A simple algorithm for 4-coloring 3-colorable planar graphs

作者：Kawarabayashi Ken ichi; Ozeki Kenta^*

来源：Theoretical Computer Science, 2010, 411(26-28): 2619-2622.

DOI：10.1016/j.tcs.2010.02.015

• 3-colorable graph
• The four color theorem

Graph coloring for 3-colorable graphs receives very much attention by many researchers in theoretical computer science. Deciding 3-colorability of a graph is a well-known NP-complete problem. So far, the best known polynomial approximation algorithm achieves a factor of O(n(0,2072)), and there is a strong evidence that there would be no polynomial time algorithm to color 3-colorable graphs using at most c colors for an absolute constant c.
In this paper, we consider 3-colorable PLANAR graphs. The Four Color Theorem (4CT) (Appel and Haken (1977)[1], Appel et al. (1977)[2], Robertson et al. (1997)[14]) gives an O(n(2)) time algorithm to 4-color any planar graph. However the current known proof for the 4CT is computer assisted. In addition, the correctness of the proof is still lengthy and complicated.
We give a very simple O(n(2)) algorithm to 4-color 3-colorable planar graphs. The correctness needs only a 2-page proof.

• 出版日期2010-6-6