4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

A triangle free planar graph can be 3-colored in linear time. Here is the URL of a paper with this result: http://people.math.gatech.edu/~thomas/PAP/lingrotpaper.pdf

If triangles are allowed the problem of testing a graph for 3 colorability becomes NP hard. So the difficulty seems to come from the presence of 3 cycles.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – singhsumit Jun 15 '11 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.