Double-critical graphs and complete minors

Ken-ichi Kawarabayashi; Anders Sune Pedersen; Bjarne Toft

paper

Double-critical graphs and complete minors

arXiv:0810.3133

Abstract

A connected $k$ -chromatic graph $G$ is double-critical if for all edges $uv$ of $G$ the graph $G - u - v$ is $(k - 2)$ -colourable. The only known double-critical $k$ -chromatic graph is the complete $k$ -graph $K_{k}$ . The conjecture that there are no other double-critical graphs is a special case of a conjecture from 1966, due to Erdős and Lovász. The conjecture has been verified for $k \leq 5$ . We prove for $k = 6$ and $k = 7$ that any non-complete double-critical $k$ -chromatic graph is 6-connected and has $K_{k}$ as a minor.