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.)



Are there any non-planar graphs containing only K(3,3) as a subgraph that are not 4-colourable?
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](http://en.wikipedia.org/wiki/Hadwiger_conjecture_%28graph_theory%29) – 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).


