MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 12 down vote accepted

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

share|cite|improve this answer
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, 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)

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.