TR00-073 Authors: Venkatesan Guruswami, Sanjeev Khanna

Publication: 13th September 2000 17:56

Downloads: 1998

Keywords:

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^{\epsilon}$ 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^{\Omega(1)}$ colors. Our proof technique

also shows that there is an $\eps_0 > 0$ such that it is NP-hard to

legally 4-color even a $(1-\eps_0)$ fraction of the edges of a

3-colorable graph.