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

详细信息    查看全文

• 作者：Ken-ichi Kawarabayashi ; Kenta Ozeki
• 关键词：3-colorable graph ; The four color theorem
• 刊名：Theoretical Computer Science
• 出版年：2010
• 出版时间：6 June 2010
• 年：2010
• 卷：411
• 期：26-28
• 页码：2619-2622
• 全文大小：238 K

文摘

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²) 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²) algorithm to 4-color 3-colorable planar graphs. The correctness needs only a 2-page proof.