Contractibility and the Hadwiger Conjecture

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