We study the complexity of the problem of graph 3-coloring 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-coloring remains NP-complete.
![[]](http://cs-www.uchicago.edu/publications/cjtcs/art/up.gif)
Volume 1999 Abstracts
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 1999
Published articles
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif){kind=logo}
Last modified: Mon May 1 14:53:14 CDT 2000