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

  • $\begingroup$ It would probably be better to ask this on cstheory.stackexchange.com as this seems to be a research-level question. $\endgroup$ – Listing Feb 20 '14 at 20:09
  • $\begingroup$ 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). $\endgroup$ – JeremyKun Feb 20 '14 at 20:53
  • 3
    $\begingroup$ 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. $\endgroup$ – Listing Feb 20 '14 at 21:22
  • $\begingroup$ Yes, but we're also given the promise that our graph is 3-colorable, so the decision problem is trivial. $\endgroup$ – 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.

  • $\begingroup$ I think this works. $\endgroup$ – JeremyKun Feb 21 '14 at 14:29

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.