8
$\begingroup$

It's obvious why any graph containing K(5) wouldn't be 4-colourable, but what about graphs containing only instances of K(3,3) to assert their non-planarity?

(Edit: By a graph "containing" another graph, I mean having it as a subgraph. Sorry for being unclear. Although now that I think about it, perhaps the word "minor" is better.)

$\endgroup$
3
  • 1
    $\begingroup$ What do you mean by contain? If I subdivide each edge of $K_5$, I get a bipartite graph $Y$. Clearly $Y$ contains $K_5$ as a subdivision and as a minor. $\endgroup$ Oct 22, 2012 at 15:01
  • 2
    $\begingroup$ I interpret the question to mean: graph that has a subgraph homeomorphic to $K_{3,3}$, but no subgraph homeomorphic to $K_5$. $\endgroup$ Oct 22, 2012 at 21:46
  • $\begingroup$ Gerry Myerson's interpretation is correct. Sorry for being unclear. $\endgroup$
    – Joe Z.
    Oct 26, 2012 at 14:45

4 Answers 4

15
$\begingroup$

There are a couple different answers to this question, depending on what question you're actually asking. You talk about a copy of $K_{3,3}$ to "assert their non-planarity," but it's unclear whether you mean this in the context of Kuratowski's Theorem (a graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3}$) or Wagner's Theorem (a graph is planar if and only if it does not contain $K_5$ or $K_{3,3}$ as a minor).

In general, subdivisions and minors are very different things: there are graphs, like the Petersen graph, which have no $K_5$ subdivision but do have a $K_5$ minor.

As Agol points out, there is a major conjecture – Hadwiger's conjecture – that claims every $K_k$-minor free graph is $(k-1)$-colourable. It's a very difficult open problem, but has been proved for the cases $k\leq 6$. In particular, your question (if you're talking about minors) is about the case $k=5$: Wagner proved way back in 1937 that this is equivalent to the Four-Colour Theorem. Since the Four-Colour Theorem is true, we can conclude that every graph with no $K_5$-minor is $4$-colourable.

What about forbidding $K_5$-subdivisions? As I mentioned above, this could have a different answer, because the class of graphs with no $K_5$-subdivision is strictly larger than the class of $K_5$-minor-free graphs. As it turns out, Hajos made a parallel conjecture in the 1940's: he suggested that every graph with no $K_k$ subdivision is $(k-1)$-colourable. However, Hajos' conjecture is false for $k\geq 7$; in fact, Erdős and Fajtlowicz showed that it fails for almost all graphs. Your question (if you're talking about subdivisions) again relates to the case $k=5$, which is actually still open. So it might be the case that every graph with no $K_5$-subdivision is $4$-colourable, but we just don't know!

For more information on these problems, see Toft's survey on Hadwiger's Conjecture (Congressus Numerantium 115 p. 249--283, 1996).

$\endgroup$
2
  • $\begingroup$ Oops! I meant Hajos both times. $\endgroup$ Oct 27, 2012 at 17:58
  • $\begingroup$ This answer helped me clear up my own misconceptions about the problem. Thanks for the detailed explanation. $\endgroup$
    – Joe Z.
    Nov 23, 2012 at 5:00
17
$\begingroup$

This follows from the Hadwiger conjecture for $k=5$. If a graph has no $K_5$ minor, then it is 4-colorable.

$\endgroup$
9
  • 3
    $\begingroup$ It's probably worth adding that according to the Wikipedia article, Hadwiger's Conjecture for $k=5$ is equivalent to the four-color theorem, and so is actually known. $\endgroup$ Oct 23, 2012 at 5:37
  • $\begingroup$ I think you misread the question --- which was very easy, of course. Teaching in Singapore for 6+ years lets me read the question without much trouble, though :-) $\endgroup$ Oct 23, 2012 at 6:48
  • 1
    $\begingroup$ Dima, I think you might have misread the question. :-) I take the expression "graphs containing only instances of K(3,3) to assert their non-planarity" to mean "graphs that are non-planar because of a K(3,3) minor, but contain no K5 minor". $\endgroup$ Oct 23, 2012 at 7:00
  • 1
    $\begingroup$ I'm interpreting "containing no K(5)" as meaning that there is no K(5) minor. This is the natural interpretation of the question given the Kuratowski characterization of planar graphs as graphs which contain no K(5) or K(3,3) minor. If Joe Zeng meant something else, then he should clarify the meaning of "containing" in his question. If he means there's no subgraph K(5), then it's probably false. $\endgroup$
    – Ian Agol
    Oct 23, 2012 at 16:26
  • 1
    $\begingroup$ @Algol Kuratowski's theorem actually characterizes planar graphs in terms of subdivisions; you're thinking of Wagner's theorem. As I explain in my answer, the distinction between subdivisions and minors is actually very important! $\endgroup$ Oct 26, 2012 at 18:26
1
$\begingroup$

Wikipedia:

As Wagner showed, every graph that has no K5 minor can be decomposed via clique-sums into pieces that are either planar or an 8-vertex Möbius ladder, and each of these pieces can be 4-colored independently of each other, so the 4-colorability of a K5-minor-free graph follows from the 4-colorability of each of the planar pieces.

From http://en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29

$\endgroup$
0
$\begingroup$

If you are looking for a non 4-colorable graph free of a $K_5$ as subgraph, the simpler way would be taking a non 4-colorable graph and adding a disjoint copy of $K_{3,3}$. One such graph is the Mycielski Graph $M_4$.

$\endgroup$
1
  • $\begingroup$ This doesn't contain $K_5$ as a subgraph, but it does contain a subdivision of $K_5$ as a subgraph (just remove the central vertex). $\endgroup$ Nov 16, 2012 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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