4 ms·
No, in fact there are graphs of arbitrary chromatic number that don’t even contain a triangle. It’s true, and quite easy to prove, that a planar graph can’t con
by intuitionist 7y ago
No, in fact there are graphs of arbitrary chromatic number that don’t even contain a triangle. It’s true, and quite easy to prove, that a planar graph can’t contain a complete subgraph on 5 vertices. But this isn’t sufficient to prove the four-color theorem.
There is a slight modification of the statement that may be correct; if you replace the condition of having a complete subgraph with that of having a complete minor, this is a very famous open problem called the Hadwiger conjecture. (It’s known to be true for the case n=5, i.e. every 5-chromatic graph has a K_5 minor.)
- Cogito 7y agoTo confirm I understand (and I think this is where I was at originally): If a graph contains K_5 then it requires at least 5 colours to colour, but if a graph does not contain K_5 then it might still require 5 colours. The example given by OscarCunningham is a great one.
- intuitionist 7y agoRight—as mathematicians say, having a K_n subgraph is a sufficient but not necessary condition for having a chromatic number of at least n. Hadwiger’s conjecture goes the other way, stating that having a K_n minor is a necessary but not sufficient condition for having a chromatic number of at least n.