Discrete Mathematics and Optimization Seminar
Jan. 26th, 2009
 On Hadwiger's Graph Colouring Conjecture David Wood University of Melbourne Hadwiger's Conjecture, which states that every graph with no \$K_t\$-minor is \$(t-1)\$-colourable, is a sweeping generalisation of the four-colour theorem, and is widely considered one of the most important open problems in graph theory. Our lack of knowledge about this conjecture is highlighted by the fact that it is even unknown whether every graph with no \$K_t\$-minor is \$O(t)\$-colourable. Consider the following relaxation of Hadwiger's Conjecture: For each \$t\$ there exists an integer \$N_t\$ such that every graph with no \$K_t\$-minor admits a vertex partition into \$\lceil A t + B \rceil\$ parts, such that each component of the subgraph induced by each part has at most \$N_t\$ vertices. Hadwiger's Conjecture corresponds to the case \$A=1\$, \$B = -1\$ and \$N_t = 1\$. Kawarabayashi and Mohar [J. Combin. Theory Ser. B, 2007] proved this relaxation with \$A= 31/2\$ and \$B=0\$ (and \$N_t\$ a huge function of \$t\$). In this talk I will prove this relaxation with \$A=7/2\$ and \$B=-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.