![]() |
![]() |
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 GraphsAdd 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. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsComputer Security Seminars Electromagnetic Communications and Sensing Research Seminar Series Biosciences seminarsOther talksUltrafast Spectroscopy and Microscopy as probes of Energy Materials Waveform modelling and the importance of multipole asymmetry in Gravitational Wave astronomy TBA TBA TBA TBC |