Wheels in planar graphs and Hajós graphs. Issue 2 (8th June 2021) - Xie, Qiqin; Xie, Shijie; Yu, Xingxing; Yuan, Xiaofan
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.