期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give a new proof showing that it is NP-hard to color a 3-colorable
graph using just four colors. This result is already known (Khanna,
Linial, Safra 1992), but our proof is novel as it does not rely on
the PCP theorem, while the earlier one does. This highlights a qualitative
difference between the known hardness result for coloring 3-colorable
graphs and the factor n hardness for approximating the
chromatic number of general graphs, as the latter result is known to
imply (some form of) PCP theorem.
Another aspect in which our proof is different is that using the
PCP theorem we can show that 4-coloring of 3-colorable graphs
remains NP-hard even on bounded-degree graphs. We point out that such
graphs can always be colored using O(1) colors by a simple greedy
algorithm, while the best known algorithm for coloring (general)
3-colorable graphs requires n(1) colors. Our proof technique
also shows that there is an \eps00 such that it is NP-hard to
legally 4-color even a (1−\eps0) fraction of the edges of a
3-colorable graph.
