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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2011 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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