We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On a Coloring Conjecture of Hajós.
- Authors
Sun, Yuqin; Yu, Xingxing
- Abstract
Hajós conjectured that graphs containing no subdivision of $$K_5$$ are 4-colorable. It is shown in Yu and Zickfeld (J Comb Theory Ser B 96:482-492, ) that if there is a counterexample to this conjecture then any minimum such counterexample must be 4-connected. In this paper, we further show that if $$G$$ is a minimum counterexample to Hajós' conjecture and $$S$$ is a 4-cut in $$G$$ then $$G-S$$ has exactly two components.
- Subjects
GRAPH coloring; LOGICAL prediction; GRAPH theory; SUBDIVISION surfaces (Geometry); INDEPENDENCE (Mathematics)
- Publication
Graphs & Combinatorics, 2016, Vol 32, Issue 1, p351
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-015-1539-0