Premium
4‐Separations in Hajós graphs
Author(s) -
Xie Qiqin,
Xie Shijie,
Yu Xingxing,
Yuan Xiaofan
Publication year - 2022
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.22751
Subject(s) - combinatorics , conjecture , mathematics , disjoint sets , counterexample , graph , subdivision , enhanced data rates for gsm evolution , discrete mathematics , computer science , geography , telecommunications , archaeology
Abstract As a natural extension of the Four Color Theorem, Hajós conjectured that graphs containing no K 5 ‐subdivision are 4‐colorable. Any possible counterexample to this conjecture with minimum number of vertices is called a Hajó s graph. Previous results show that Hajós graphs are 4‐connected but not 5‐connected. A k ‐separation in a graph G is a pair ( G 1 , G 2 ) of edge‐disjoint subgraphs of G such that ∣ V ( G 1 ∩ G 2 ) ∣ = k , G = G 1 ∪ G 2 , and G i ⊈ G 3 − ifor i = 1 , 2 . In this paper, we show that Hajós graphs do not admit a 4‐separation ( G 1 , G 2 ) such that ∣ V ( G 1 ) ∣ ≥ 6 and G 1 can be drawn in the plane with no edge crossings and all vertices in V ( G 1 ∩ G 2 ) incident with a common face. This is a step in our attempt to reduce Hajós' conjecture to the Four Color Theorem.