Clique Minors in Double-critical Graphs

Abstract

A connected $t$-chromatic graph $G$ is \dfn{double-critical} if $G\backslash \{u,v\}$ is $(t-2)$-colorable for each edge $uv\in 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\ge 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 $K_t$ minor and verified their conjecture for $t\le 7$. Albar and Gonçalves recently proved that every double-critical $8$-chromatic graph contains a $K_8$ minor, and their proof is computer-assisted. In this paper we prove that every double-critical $t$-chromatic graph contains a $K_t$ minor for all $t\le 9$. Our proof for $t\le 8$ is shorter and computer-free.

11 pages, to appear in J. Graph Theory

References in corpus (1)

• On triangles in K_r-minor free graphs

Cited by in corpus (1)

• Double-critical graph conjecture for claw-free graphs