The smallest hard-to-color graph for algorithm DSATUR (Q5959099)

A graph \(G\) is said to be slightly hard-to-color (SHC) with respect to an algorithm \(A\) if for some implementation of \(A\) the number \(A(G)\) of colors is greater than the chromatic number \(\chi(G)\). A graph is said to be hard-to-color (HC) if every implementation of the algorithm results in a non-optimal colornig. In Section 2, the authors review the classes of graphs which are colored optimally by the algorithm DSATUR (a most popular vertex-coloring algorithm). In Section 3, a simplification of DSATUR is introduced, namely algorithm saturation largest-first (SLF). The SLF algorithm is much easier to analyze than DSATUR. In Section 4, the main result of this paper is proved: the authors exhibit a precise graph which is the unique smallest HC graph for the DSATUR algorithm.