Arya Bhatta Journal of Mathematics and Informatics
  • Year: 2018
  • Volume: 10
  • Issue: 2

3-Colorable planar graphs

  • Author:
  • A. Ramesh Kumar1, G. Kavitha2
  • Total Page Count: 4
  • Page Number: 273 to 276

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.

Abstract

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.

Keywords

The Four color Theorem, 3-colorable graph