What is about 4-COLORING of planar graph. We know that each planar graph is 4-COLORABLE is it easy to find 4-COLORING.
The polynomial, namely n^4 algorithm was given by K. Appel, W. Haken in 1989. K. Appel, W. Haken, "Every planar map is four colorable", Contemp. Math. 98, 1-741
The algorithm is based on their original proof.
Then their result was improved by Robertson, Sanders, Seymour, Thomas in STOC-96 paper "Efficiently four-coloring planar graphs" and this algorithm has a quadratic complexity.
What is interesting that a problem of 4-COLORING is NP-hard for a 3-colorable graph (meaning given a graph G, which is known to be 3-COLORABLE, find 4-COLORING of it)
This result was prooved in 1993 by Khanna, Linial, Safra, "On the hardness of approximating the chromatic number", 2nd Israel Symposium on Theory and Computing Systems (ISTCS). Their proof uses PCP theorem. Their result immediately generalize to NP-hardness of k + 2 floor(k/3)-1 coloring of k-colorable graphs.
In 2000 Guruswami and Khanna in their paper presented at IEEE CCC gave a nice proof of NP-hardness of 4-COLORABILITY without use of the PCP theorem. Actually they proved even stronger result: 4-COLORING is NP-hard for degree-bounded 3-COLORABLE graph
Another, interesting result about coloring (not just 4-coloring). There does not exist a polynomial algorithm which approximates coloring problem with the factor better then n^\epsilon, for some \epsilon. Very easy to comprehend explanation of the proof (as well many other approximation-hard results) is in excellent a bok chapter about PCP theorem written by Stefan Hougardy