Contractibility and the Hadwiger Conjecture

Details Contractibility and the Hadwiger Conjecture Contractibility and the Hadwiger Conjecture

2008-11-13

arxiv.org/abs/0811.2012v2

European J. Combinatorics 31.8:2102-2109, 2010

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Contractibility and the Hadwiger Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Contractibility and the Hadwiger Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Contractibility and the Hadwiger Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-434513