For the vertex coloring problem COL, we conducted experiments on the classical DIMACS benchmark graphs used in most of the best coloring methods for this problem [1]}, [2]}. These instances can be separated into two categories: easy instances and difficult instances. For the easy instances, most recent heuristics can reach the chromatic number (or its best known upper bound) in a short amount of time, while for the difficult instances, no single algorithm is able to reach the chromatic number or the best known result for all these graphs. In this section, we only report the results for the most difficult instances. The results for the easy DIMACS instances are summarized in Appendix .
