Premium
Wheels in planar graphs and Hajós graphs
Author(s) -
Xie Qiqin,
Xie Shijie,
Yu Xingxing,
Yuan Xiaofan
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22687
Subject(s) - conjecture , planar graph , mathematics , combinatorics , counterexample , subdivision , graph , planar , discrete mathematics , computer science , geography , computer graphics (images) , archaeology
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.