Contractibility and the Hadwiger Conjecture

Consider the following relaxation of the Hadwiger Conjecture: For each tt there exists NtNt such that every graph with no KtKt-minor admits a vertex partition into ⌈αt+β⌉⌈αt+β⌉ parts, such that each component of the subgraph induced by each part has at most NtNt vertices. The Hadwiger Conjecture corresponds to the case α=1α=1, β=−1β=−1 and Nt=1Nt=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β=0 (and NtNt a huge function of tt). 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)(t+1)-connected graph contains a KtKt-minor, and (3) a new sufficient condition for a graph to have a set of edges whose contraction increases the connectivity.