Contractibility and the Hadwiger Conjecture

AbstractConsider the following relaxation of the Hadwiger Conjecture: For each t there exists Nt such that every graph with no Kt-minor admits a vertex partition into ⌈αt+β⌉ parts, such that each component of the subgraph induced by each part has at most Nt vertices. The Hadwiger Conjecture corresponds to the case α=1, β=−1 and Nt=1. Kawarabayashi and Mohar [K. Kawarabayashi, B. Mohar, A relaxed Hadwiger’s conjecture for list colorings, J. Combin. Theory Ser. B 97 (4) (2007) 647–651. URL: http://dx.doi.org/10.1016/j.jctb.2006.11.002] proved this relaxation with α=312 and β=0 (and Nt a huge function of t). This paper proves this relaxation with α=72 and β=−32. The main ingredients in the proof are: (1) a list colouring argument due to Kawarabayashi and Mohar, (2) a recent result of Norine and Thomas that says that every sufficiently large (t+1)-connected graph contains a Kt-minor, and (3) a new sufficient condition for a graph to have a set of edges whose contraction increases the connectivity