# A conjectured criterion for 4-colorable graphs

I tried to find a solution to this in the web but couldn't. Can you tell me if the following sentence is correct or else give me a counterexample?

$G$ is $4$-colorable if and only if each sub-graph $G'$ in $G$ is not isomorphic to $K_5$. At first glance it seems to be related to the four color theorem but it is not exactly a planar graph (e.g. $3\times 3$ complete bipartite graph) so it is not identical to FCT. Any ideas?

This is false. In fact, there are graphs that contain no K3's but have arbitrarily high chromatic number.

See this wiki article for one such construction http://en.wikipedia.org/wiki/Mycielskian

• It's even falser :-) In fact, there are graphs with high girth and high chromatic number. A graph with high girth looks like a tree around any vertex, so it avoids much more than just triangles. Proving that such graphs exist is perhaps even simpler than the explicit construction by Mycielski; it's basically a counting argument. – Alon Amit Sep 19 '10 at 23:23
• @Alon - I was familiar with this fact, but your comment made me look around a little, and I found math.auckland.ac.nz/Research/Reports/Series/531.pdf, which is a brief proof of the original result (due to Erdős). It is one of the more counterintuitive results I know of from graph theory. – Eric Tressler Sep 20 '10 at 2:30
• Thanks smart people! (Although it means i will probably fail the test but I guess sometimes you learn things the hard way) – stavnir Sep 20 '10 at 17:17

If you make it "G is 4-colorable if it has no $K_5$-minor", you are looking for Hadwiger's conjecture (which is true for $K_5$-minor, though you need the 4 color theorem to prove it)

• It's not an iff condition, just one way. There are plenty of graphs that have $K_5$ minors and are colorable with as few as two colors; for instance, the graph formed by adding a vertex in the middle of each edge of $K_5$. – David Eppstein 0 secs ago – David Eppstein Sep 20 '10 at 0:09
A related (open) statement is the $n=4$ case of Hadwiger conjecture, that a graph is $n$-colorable if [not only if, as by David's comment] it doesn't have $K_{n+1}$ as a minor (graph obtained by contracting some edges of a subgraph). Actually, as explained in wikipedia, the $n=4$ case was proved by Wagner in 1937 to be a consequence of the $4$-colour theorem (then a conjecture), so that it is actually true.
• As I commented on another answer, "iff" is incorrect here. It's possible to not have a $K_{n+1}$ minor and still be colorable with $n$ or fewer colors, and it's possible to have a $K_{n+1}$ minor and have chromatic number strictly less than $n$. – David Eppstein Sep 20 '10 at 0:12