An approximate version of Hadwiger's conjecture for claw-free graphs

Thursday, September 25, 2008 -
2:30pm to 4:30pm
Hadwiger's conjecture states that if a graph is not $t$-colorable then it contains the complete graph on $t+1$ vertices as a minor. The case $t=4$ is equivalent to the four color theorem and the case $t=5$ was proved by Robertson, Seymour, and Thomas with the use of the four color theorem. For $t>5$, the conjecture remains open. Reed and Seymour have also proved that Hadwiger's conjecture holds for line graphs and in a recent work with Maria Chudnovsky we proved that Hadwiger's conjecture holds for a proper superset of the class of line graphs, known as the class of quasi-line graphs (graphs where the neighbor set of every vertex is the union of two cliques).A graph is claw-free if it does not have a vertex with three pairwise nonadjacent neighbors. The class of claw-free graphs is a proper superset of the class of quasi-line graphs. In this talk I will outline the proof of a weakened version of Hadwiger's conjecture for claw-free graphs. The proof uses a structure theorem from a recent work of Chudnovsky and Seymour. At the end of the talk I will discuss the progress that has been made on the actual Hadwiger's conjecture for claw-free graphs. This is a joint work with Maria Chudnovsky.
Speaker: