Sách Double-critical graphs and complete minors

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 Kk. The conjecture that there are no other double- critical graphs is a special case of a conjecture from 1966, due to Erd˝os and Lov´asz. 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.