University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs

Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Johannes Carmesin.

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\geq 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree ${O(t (log t)0.5)}$ $$ and hence is $O(t (log t)0.5)$ $$-colorable. In a recent breakthrough, Norin, Song, and Postle proved that every graph with no $K_t$ minor is $O(t log t)c)$ $$-colorable for every $c > 0.25$, Subsequently Postle showed that every graph with no $K_t$ minor is $O(t (log log t)6)$ $ $ -colorable. We improve upon this further by showing that every graph with no $K_t$ minor is $O(t log log t)$-colorable. Our main technical result yields this as well as a number of other interesting corollaries. A natural weakening of Hadwiger’s Conjecture is the so-called Linear Hadwiger’s Conjecture that every graph with no $K_t$ minor is $O(t)$-colorable. We prove that Linear Hadwiger’s Conjecture reduces to small graphs. In 2003, Kühn and Osthus proved that Hadwiger’s Conjecture holds for graphs of girth at least five (provided that $t$ is sufficiently large). In 2005, Kühn and Osthus extended this result to the class of $K_{s,s}$-free graphs for any fixed positive integer $s\geq 2$. Along this line, we show that Linear Hadwiger’s Conjecture holds for the class of $K_r$-free graphs for every fixed $r$. This is joint work with Luke Postle.

This talk is part of the Combinatorics and Probability Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.