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

<p>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. </p>

CC BY-SA 3.0
2011-06-15T04:06:29.143Z
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.
singhsumit
CC BY-SA 3.0
2011-06-11T17:03:03.913Z
2011-06-11T17:03:03.913Z
Kristal
<p>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:</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

<ds.algorithms><graph-algorithms><approximation-algorithms><graph-colouring>
3 colorable graphs
singhsumit
# 3 colorable graphs

(Asked by: username_0 on 2011-06-11)

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.

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, graph-colouring


---

## 1 answers

### Answer by username_1 on 2011-06-11. Score: 4

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.

> **Comments:**
> **username_0**: 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.  

---

