Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs

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

• Michelle Delcourt, Toronto
• Thursday 14 October 2021, 15:00-16:00
• https://bham-ac-uk.zoom.us/j/87124623071.

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.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• https://bham-ac-uk.zoom.us/j/87124623071

Note that ex-directory lists are not shown.