# Is it easy to color 3-colorable triangle-free graphs?

Grötzsch's theorem states that every planar triangle-free graph $G$ has a 3-coloring, and it is known how to efficiently find such a coloring. Moreover, if the planar condition is dropped, it is known that $G$ can have arbitrarily large chromatic number (via the Mycielskian construction).

My question is: if we're guaranteed that $G$ is triangle-free and 3-colorable, is there a known way to efficiently find a 3-coloring of $G$?

There is a lot of work in showing things like the NP-hardness of 4-coloring a 3-colorable graph, so I don't think it's obvious...

• It would probably be better to ask this on cstheory.stackexchange.com as this seems to be a research-level question. – Listing Feb 20 '14 at 20:09
• I chose to post here first, because I am afraid it is so obvious as to be trivial (I tend to ask a lot of stupid questions). – JeremyKun Feb 20 '14 at 20:53
• If it helps, deciding if a triangle-free graph of max-degree 4 is 3-colorable is np-complete ( dl.acm.org/citation.cfm?id=246916 ). If there was some polynomial algorithm to find an actual 3-coloring in triangle-free 3-colorable graphs, it could probably also be used to decide if a triangle-free graph is 3-colorable. – Listing Feb 20 '14 at 21:22
• Yes, but we're also given the promise that our graph is 3-colorable, so the decision problem is trivial. – JeremyKun Feb 20 '14 at 23:20

Let me elaborate on my comment. Assume we have some polynomial algorithm 3COL, which returns a valid 3-coloring 3COL(G) of any triangle-free 3-colorable graph $G$ in polynomial time.

As 3COL is polynomial there are some $a,b,c \in \mathbb{N}$, such that on a graph with $n$ vertices, 3COL will always therminate after $a n^b+c$ instructions.

I claim that there is a polynomial algorithm to decide if a given triangle-free graph is 3-colorable (in particular it will decide if the graph is not 3-colorable):

1. Let $G$ be any triangle-free graph on $n$ vertices.
2. We execute $a n^b+c+1$ instructions of 3COL(G). If the algorithm doesn't terminate $G$ has no 3-coloring.
3. Assume the algorithm terminates with some coloring. Either it is valid (then we are done and the graph is 3-colorable) or it is invalid. If it is invalid, we know that the graph can't be 3-colorable as 3COL is correct on 3-colorable triangle-free graphs.

This algorithm runs in polynomial time and decides the $NP$-complete problem if a triangle-free graph is 3-colorable, thus it can't exist unless $P=NP$.

I didn't see this kind of argument before, so let me know if you see some gap in my proof.

• I think this works. – JeremyKun Feb 21 '14 at 14:29