On the connectivity of minimum and minimal counterexamples to Hadwiger's Conjecture

The main result of this paper is the following: Any minimal counterexample to Hadwiger's Conjecture for the k-chromatic case is -connected.This improves the previous known bound due to Mader [W. Mader, Über trennende Eckenmengen in homomorphiekritischen Graphen, Math. Ann. 175 (1968) 243–252], which says that any minimal counterexample to Hadwiger's Conjecture for the k-chromatic case is 7-connected for k⩾7. This is the first result on the vertex connectivity of minimal counterexamples to Hadwiger's Conjecture for general k.Consider the following problem: There exists a constant c such that any ck-chromatic graph has a Kk-minor. This problem is still open, but together with the recent result in [T. Böhme, K. Kawarabayashi, J. Maharry, B. Mohar, Linear connectivity forces large complete bipartite graph minors, preprint], our main result implies that there are only finitely many minimal counterexamples to the above problem when c⩾27. This would be the first step to attach the above problem.We also prove that the vertex connectivity of minimum counterexamples to Hadwiger's Conjecture is at least -connected.This is also the first result on the vertex connectivity of minimum counterexamples to Hadwiger's Conjecture for general k.