Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
add comment

3 Answers

up vote 11 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 http://en.wikipedia.org/wiki/Mycielskian

share|improve this answer
4  
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
1  
@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
add comment

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|improve this answer
5  
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
add comment

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|improve this answer
1  
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
add comment

Your Answer

 
discard

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.