# 3 colorable graphs

I was trying to understand the underlying difficulty of coloring 3 colorable graphs with as least number of colors as possible. Though i am aware of hardness result of coloring it with 4 colors, i couldn't characterize these graphs much. My question is:

What are the different characteristics of 3 colorable graph? Also what makes them different from 4 colorable graphs (or others), apart from the fact the 3 colorable graphs may not necessarily have $K_4$ as minor whereas 4 colorable graphs will have?

I have tried to work on these but couldn't come with some argument of my own and the materials i got discussed algorithms like $n^{\epsilon}$-approximation through SDP which i have read but still i feel i am lacking the insight to the problem.

• Thanks for the answer. i know about the theorem you stated which came in 1959 and resulted in an $O(n^2)$ algorithm and your reference has improved it. However these are special cases and am looking for some more general characteristic which may result in exponential time algorithm. Inconstructive proofs are also welcome. Jun 15, 2011 at 4:06