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.
【 预 览 】
附件列表
Files
Size
Format
View
Coloring graphs with no k5-subdivision: disjoint paths in graphs