2019/11/24 by Qiqin Xie, Xie, Qiqin, Shijie Xie +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1911.10464
arxiv created 2019/11/24 · openalex publication_date 2019/11/24 · arxiv updated 2019/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It was conjectured by Hajós that graphs containing no K5-subdivision are 4-colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture, called Hajós graph, is 4-connected but not 5-connected. In this paper, we show that if a Hajós graph admits a 4-cut or 5-cut with a planar side then the planar side must be small or contains a special wheel. This is a step in our effort to reduce Hajós' conjecture to the Four Color Theorem.