Contractibility and the Hadwiger Conjecture
Author:
Preprint
Abstract
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{\alpha t+\beta}$ 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 $\alpha=1$, $\beta=-1$ and $N_t=1$. Kawarabayashi and Mohar [\emph{J. Combin. Theory Ser. B}, 2007] proved this relaxation with $\alpha={31/2}$ and $\beta=0$ (and $N_t$ a huge function of $t$). This paper proves this relaxation with $\alpha={7/2}$ and $\beta=-{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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Another proof of the 5-choosability of -minor-free graphsDiscrete Mathematics, 2008
- A relaxed Hadwiger's Conjecture for list coloringsJournal of Combinatorial Theory, Series B, 2007
- High connectivity keeping sets in graphs and digraphsDiscrete Mathematics, 2005
- A Survey on Contractible Edges in Graphs of a Prescribed Vertex ConnectivityGraphs and Combinatorics, 2002
- The Extremal Function for Complete MinorsJournal of Combinatorial Theory, Series B, 2001
- The Four-Colour TheoremJournal of Combinatorial Theory, Series B, 1997
- Every Planar Graph Is 5-ChoosableJournal of Combinatorial Theory, Series B, 1994
- Hadwiger's conjecture forK 6-free graphsCombinatorica, 1993
- Generalizations of critical connectivity of graphsDiscrete Mathematics, 1988
- Eine Eigenschaft der Atome endlicher GraphenArchiv der Mathematik, 1971