# Does "$G$ contains no $K_n$" imply "$G$ is $n-$colorable"?

This question occurs to me while I was thinking about the Four Color Theorem and Five Color Theorem. If we can prove that "$$G$$ contains no $$K_n$$" (where $$K_n$$ is the complete graph with $$n$$ nodes) implies "$$G$$ is $$n-$$colorable," then we can show that any planar graph is $$5-$$colorable, as any planar graph contains no $$K_5$$.

I would assume that this question is already answered somewhere, but I couldn't find anything.

Thanks for any help!

• For example, see the second question under "Related" to the right: math.stackexchange.com/questions/696164/… Jan 17, 2021 at 0:33
• For $n=3$ the smallest counterexample has $11$ vertices and is called the Grötzsch graph.
– bof
Jan 17, 2021 at 1:50
• Thank you both! They are very helpful :) Jan 17, 2021 at 1:57

The clique number $$\omega(G)$$ of a graph is the largest size of a clique in it. Your question is equivalent to asking whether $$\chi(G) \le \omega(G) + 1$$ where $$\chi(G)$$ is the chromatic number. Unfortunately this is known to be false: in particular, it's known that there exist triangle-free graphs (hence $$\omega(G) = 2$$) with arbitrarily large chromatic number; see, for example, here.
A variant of this problem where we ask for $$K_n$$ minors rather than $$K_n$$ subgraphs is apparently an open problem, the Hadwiger conjecture.