Coloring graphs with no k5-subdivision: disjoint paths in graphs

Graph coloring;Hajos conjecture

Xie, Qiqin ; Yu, Xingxing Mathematics Blekherman, Grigoriy Iliev, Plamen Yu, Josephine Huang, Hao ; Yu, Xingxing

University:Georgia Institute of Technology

Department:Mathematics

关键词: Graph coloring;    Hajos conjecture;   

Others  :  https://smartech.gatech.edu/bitstream/1853/62659/1/XIE-DISSERTATION-2019.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

The Four Color Theorem states that every planar graph is 4-colorable. Hajos conjectured that for any positive integer k, every graph containing no K_{k+1}-subdivision is k-colorable. However, Catlin disproved Hajos conjecture for k>=6. It is not hard to prove that the conjecture is true for k<=3. Hajos' conjecture remains open for k=4 and k=5. We consider a minimal counterexample to Hajos conjecture for k=4. We use Hajos graph to denote such counterexample. One important step to understand graphs containing K5-subdivisions is to solve the topological H problem. We characterize graphs with no topological H, and the characterization is used by He, Wang, and Yu to show that graph containing no K5-subdivisions is planar or has a 4-cut, establishing conjecture of Kelmans and Seymour. Besides the topological H problem, we also obtained some further structural information of Hajos graphs.