# 4-colorable graphs

Hey guys, 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 iff each sub-graph G' in G is not isomorphic to K5. At first glance it seems to be related to the four color theorem but it is not exactly a planar graph (e.g. 3x3 complete bipartite graph) so it is not identical to FCT. Any ideas?

Thanks!

-

## 3 Answers

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)

(edited after comments)

-
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
Feeling stupid. I totally deserve that one... :-D Thank you !!!! –  Nathann Cohen Sep 20 '10 at 5:32

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