Google Scholar

Thursday, August 04, 2005

Use of PCP theorem

As it was proved by Khanna, Linial and Safra in 2000, it is NP-hard to color 3-colorable graph using 4-colors. That proof used PCP-theorem.
Last year they found an elegant proof of the same result which does not rely on PCP theorem. See
V. Guruswami, S. Khanna, On the hardness of 4-coloring of 3-colorable graph, SIAM Journal on Discrete Mathematics, 18, 1 (2004)
But PCP theorem is still needed to prove NP-hardness of 4-colorability of 3-colorable graph for bounded degree graphs.