2
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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

$\endgroup$
3
  • 5
    $\begingroup$ 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. $\endgroup$
    – Alon Amit
    Sep 19 '10 at 23:23
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 20 '10 at 2:30
  • $\begingroup$ Thanks smart people! (Although it means i will probably fail the test but I guess sometimes you learn things the hard way) $\endgroup$
    – stavnir
    Sep 20 '10 at 17:17
10
$\begingroup$

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)

$\endgroup$
2
  • 5
    $\begingroup$ 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 $\endgroup$ Sep 20 '10 at 0:09
  • $\begingroup$ Feeling stupid. I totally deserve that one... :-D Thank you !!!! $\endgroup$ Sep 20 '10 at 5:32
6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$ Sep 20 '10 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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