Heuristics Versus Completeness for Graph Coloring.
Jörg Rothe · 2000
We study the complexity of the problem 3-Colorability when restricted to those input graphs on which a given graph coloring heuristic is able to solve the problem. The heuristics we consider include the sequential algorithm traversing the vertices of the graph in various orderings (e.g., by decreasing degree or in the recursive smallest-last order) as well as Wood's algorithm. For each heuristic considered here, we prove that the corresponding restriction of 3-Colorability remains NP-complete. 1 Introduction Graph coloring problems are of great importance in both theory and applications and have been intensely studied during the past century. Applications of constructing a graph coloring with as few colors as possible arise, for instance, in scheduling and partitioning problems (see Garey and Johnson [GJ79]). Unfortunately, the (optimization) problem of finding the chromatic number of a given graph is very complex, and even the (decision) problem of determining whether or not a given...