4-Separations in Hajós Graphs

Abstract

As a natural extension of the Four Color Theorem, Hajós conjectured that graphs containing no $K_5$-subdivision are 4-colorable. Any possible counterexample to this conjecture with minimum number of vertices is called a {\it Hajós graph}. Previous results show that Hajós graphs are 4-connected but not 5-connected. A $k$-separation in a graph $G$ is a pair $(G_1,G_2)$ of edge-disjoint subgraphs of $G$ such that $|V(G_1\cap G_2)|=k$, $G=G_1\cup G_2$, and $G_i⊈G_{3-i}$ for $i=1,2$. In this paper, we show that Hajós graphs do not admit a 4-separation $(G_1,G_2)$ such that $|V(G_1)|\ge 6$ and $G_1$ can be drawn in the plane with no edge crossings and all vertices in $V(G_1\cap G_2)$ incident with a common face. This is a step in our attempt to reduce Hajós' conjecture to the Four Color Theorem.

25 pages, 1 figure