1
$\begingroup$

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!

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

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Very interesting. Thank you so much for your answer and information! $\endgroup$ Jan 17, 2021 at 0:38
  • $\begingroup$ @bof: oh, I see, my bad. $\endgroup$ Jan 17, 2021 at 2:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .