1Asst. Professor, Srimad Andavan Arts & Science College, Trichy-05, Tamilnadu, India, E-mail: andavanmathsramesh@gmail.com
2Asst. Professor, Kongunadu College of Engineering and Technology, Tholurpatti, Thottiam, Tamilnadu, kavipraba18@gmail.com
Online published on 6 October, 2018.
In this paper, we consider 3-colorable planar graphs. The Four Color Theorem (4CT) gives an O(n2) time algorithm to 4-color any planar graph. Graph coloring for 3-colorable graphs receives very much attention by many researchers in theoretical computer science. Deciding 3-colorablility of a graph is a well-known NPcomplete problem. We give a very simple O (n2) time algorithm to 4-color 3-colorable planar graphs.
The Four color Theorem, 3-colorable graph
