2016/03/22 by Martin Rolek, Zi‐Xia Song, Rolek, Martin +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1603.06964
openalex publication_date 2016/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A connected t-chromatic graph G is \dfndouble-critical if G \backslash\u, v\ is (t-2)-colorable for each edge uv∈ E(G). A long standing conjecture of Erdős and Lovász that the complete graphs are the only double-critical t-chromatic graphs remains open for all t≥6. Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well-known Hadwiger's conjecture, Kawarabayashi, Pedersen and Toft proposed a weaker conjecture that every double-critical t-chromatic graph contains a Kt minor and verified their conjecture for t≤7. Albar and Gonçalves recently proved that every double-critical 8-chromatic graph contains a K8 minor, and their proof is computer-assisted. In this paper we prove that every double-critical t-chromatic graph contains a Kt minor for all t≤9. Our proof for t≤8 is shorter and computer-free.