论文标题
Hajós图中的4分离
4-Separations in Hajós Graphs
论文作者
论文摘要
作为四种颜色定理的自然扩展，Hajós认为包含$ k_5 $ -subdivision的图形是4色。与最少数量的顶点数量的任何可能的反例称为{\ ithajósgraph}。先前的结果表明，Hajós图是4连接但没有连接的。图$ g $中的a $ k $ - 分别是$ g $的边缘 - 偶数子图的一对$（g_1，g_2）$，这样$ | v（g_1 \ cap g_2）| = k $，$ g = g_1 \ g_1 \ cup cup g_1 g_2 $，$ g_i \ g_i \ g_i \ not \ subseteeq g_ $ i = $ I = $ i = $ i = $ I = $ I = $ i = $ i = $ i = $ I = 3-}在本文中，我们表明Hajós图不承认4分钟$（g_1，g_2）$，因此可以在没有边缘交叉点上绘制$ | v（g_1）| \ ge 6 $和$ g_1 $，而无需$ v（g_1 \ cap g_2）$带有常见的面孔。这是我们试图将Hajós的猜想减少到四种颜色定理的一步。
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\not\subseteq 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.
