The smallest hard-to-color graph (Q1185079)

For a given approximate vertex coloring algorithm, a graph is said to be slightly-hard-to-color if some implementation of the algorithm uses more colors than the chromatic number. Similarly, a graph is said to be hard- to-color if every implementation of the algorithm results in a non- optimal coloring. The authors study smallest such graphs for the general sequential algorithm and the sequential largest-first algorithm. The main result is that for the latter heuristic there exists a unique smallest hard-to-color graph with 7 vertices. The concept of the smallest hard-to- color graph leads to a new characterization of approximation of graph coloring heuristics.