The smallest hard-to-color graph for algorithm DSATUR Original Research Article

For a given approximate coloring algorithm a graph is said to be slightly hard-to-color (SHC) if some implementation of the algorithm uses more colors than the chromatic number. Similarly, a graph is said to be hard-to-color (HC) if every implementation of the algorithm results in a non-optimal coloring. In the paper, we study the smallest of such graphs for the DSATUR vertex coloring algorithm.