Wheels in planar graphs and Hajós graphs. Issue 2 (8th June 2021)

• Record Type: Journal Article
• Authors: Xie, Qiqin; Xie, Shijie; Yu, Xingxing; Yuan, Xiaofan
• Is Part Of: Journal of graph theory. Volume 98:Issue 2(2021)
• Page Start: 179
• Page End: 194
• Publication Date: 2021-06-08
• Subjects: coloring -- disjoint paths -- graph subdivision -- wheels; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22687
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: It was conjectured by Hajós that graphs containing no K 5 ‐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.