Double-critical graphs and complete minors (Q976747)

Summary: 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 doublecritical graphs is a special case of a conjecture from 1966, due to Erdős and Lovász. The conjecture has been verified for \(k\) at most 5. We prove for \(k=6\) and \(k=7\) that any non-complete double-critical \(k\)-chromatic graph is 6-connected and contains a complete \(k\)-graph as a minor.