4-Separations in Hajós Graphs

2020/04/26 by Qiqin Xie, Xie, Qiqin, Shijie Xie +5
Mathematics · #05C10 #05C40 #05C83 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C10 #msc:05C40 #msc:05C83

paper · pdf · doi:10.48550/arxiv.2004.12468

25 pages, 1 figure

arxiv created 2020/04/26 · arxiv updated 2020/04/28

Abstract

As a natural extension of the Four Color Theorem, Hajós conjectured that graphs containing no K₅-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₁,G₂) of edge-disjoint subgraphs of G such that |V(G₁∩ G₂)|=k, G=G₁∪ G₂, and G_i\not⊆ G_3-i for i=1,2. In this paper, we show that Hajós graphs do not admit a 4-separation (G₁,G₂) such that |V(G₁)|≥ 6 and G₁ can be drawn in the plane with no edge crossings and all vertices in V(G₁∩ G₂) incident with a common face. This is a step in our attempt to reduce Hajós' conjecture to the Four Color Theorem.

Related

• Wheels in planar graphs and Hajós graphs
• Topological containment of the 5-clique minus an edge in 4-connected graphs
• Mathematical Proofs of Two Conjectures: The Four Color Problem and The Uniquely 4-colorable Planar Graph
• A Simple Proof of the Four-Color Theorem
• On a conjecture concerning 4-coloring of graphs with one crossing