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.
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.
