# 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