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 $\ceil{α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 [\emph{J. Combin. Theory Ser. B}, 2007] 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.

No reviews yet.

No comments yet.