Published by MIT Press. Copyright 2000 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.

Abstract

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.

• Preformatted versions of the article
  • DVI (70,700 bytes)
  • PostScript (381,060 bytes)
  • PDF (143,245 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX (cj00-01.tex, 50,863 bytes)
  • BIBTeX (cj00-01.bib, 3,304 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 165 bytes)
  • Self citation in BIBTeX (311 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.2000.001

---

Volume 1999, Article 11 Article 2
Volume 1999 Published articles