The Four Color Theorem states that a planar graph requires at most four colors to be proper colored.
The Kuratowski's Theorem states that a graph is planar if, and only if, it doesn't have a subgraph which is a subdivision of either $K_{3,3}$ or $K_5$.
We can conclude then that a graph that requires at least five colors to be proper colored must have a subgraph which is a subdivision of either $K_{3,3}$ or $K_5$.
$K_5$ is, itself, a graph that requires five colors, but $K_{3,3}$ requires only two. So my question is: is there a graph that requires at least five colors to be colored that doesn't have a subgraph which is a subdivision of $K_5$? (Of course, that would force it to have a subdivision of $K_{3,3}$)
I know it's equivalent to the Four Color Theorem that "graphs that require five colors must have a minor of a $K_5$", but I don't think that answers my question, since subdivisions are just a particular case of minor. I might be wrong, though.
Best Answer
It is unknown whether such a graph exists. Originally, Hajós conjectured that for all $k$, all graphs with no subdivision of $K_{k+1}$ are $k$-colorable. It is now known that for $k\ge 6$, this conjecture is false. For $k=3$, the conjecture is proven; for $k=4$ (this question) and $k=5$, it is still open.
One of the most recent papers with partial progress on this conjecture seems to be Wheels in planar graphs and Hajós graphs by Qiqin Xie, Shijie Xie, Xingxing Yu, and Xiaofan Yuan. Here (as in many other papers) a Hajós graph is defined to be a minimal counterexample to the conjecture: a graph $G$ such that
The ultimate hope, of course, is to prove that $G$ cannot exist - or to find an example. To make partial progress, researchers try to prove more and more properties of Hajós graphs, which should make it easier to reach a contradiction, or to construct a Hajós graph.