2 deleted 1 characters in body

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, HalmosHajos' 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).

1

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, Halmos' 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).