Wheels in planar graphs and Hajós graphs | Zendy

Xie Qiqin | Zendy; Xie Shijie | Zendy; Yu Xingxing | Zendy; Yuan Xiaofan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research