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...
 A: 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):


*

*Let $G$ be any triangle-free graph on $n$ vertices.

*We execute $a n^b+c+1$ instructions of 3COL(G). If the algorithm doesn't terminate $G$ has no 3-coloring.

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