2016/06/17 by Martin Rolek, Zi‐Xia Song, Rolek, Martin +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1606.05507
openalex publication_date 2016/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hadwiger's conjecture from 1943 states that for every integer t≥1, every graph either can be t-colored or has a subgraph that can be contracted to the complete graph on t+1 vertices. As pointed out by Paul Seymour in his recent survey on Hadwiger's conjecture, proving that graphs with no K7 minor are 6-colorable is the first case of Hadwiger's conjecture that is still open. It is not known yet whether graphs with no K7 minor are 7-colorable. Using a Kempe-chain argument along with the fact that an induced path on three vertices is dominating in a graph with independence number two, we first give a very short and computer-free proof of a recent result of Albar and Gonçalves and generalize it to the next step by showing that every graph with no Kt minor is (2t-6)-colorable, where t∈\7,8,9\. We then prove that graphs with no K8- minor are 9-colorable and graphs with no K8^= minor are 8-colorable. Finally we prove that if Mader's bound for the extremal function for Kp minors is true, then every graph with no Kp minor is (2t-6)-colorable for all p≥5. This implies our first result. We believe that the Kempe-chain method we have developed in this paper is of independent interest.