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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
13
$\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

Improve this answer
$\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
    Commented Sep 19, 2010 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$
    – Eric Tressler
    Commented Sep 20, 2010 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
    Commented Sep 20, 2010 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)

Improve this answer
$\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$
    – David Eppstein
    Commented Sep 20, 2010 at 0:09
  • $\begingroup$ Feeling stupid. I totally deserve that one... :-D Thank you !!!! $\endgroup$
    – Nathann Cohen
    Commented Sep 20, 2010 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.

Improve this answer
$\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$
    – David Eppstein
    Commented Sep 20, 2010 at 0:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .