2020/04/22 by Norin, Sergey, Postle, Luke
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2004.10367
In 1943, Hadwiger conjectured that every graph with no Kt minor is (t-1)-colorable for every t≥ 1. While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. In the 1980s, Kostochka and Thomason independently proved that every graph with no Kt minor has average degree O(t√(log t)) and thus is O(t√(log t))-list-colorable. Recently, the authors and Song proved that every graph with no Kt minor is O(t(log t)β)-colorable for every β> \frac 1 4. Here, we build on that result to show that every graph with no Kt minor is O(t(log t)β)-list-colorable for every β> \frac 1 4. Our main new tool is an upper bound on the number of vertices in highly connected Kt-minor-free graphs: We prove that for every β> \frac 1 4, every Ω(t(log t)β)-connected graph with no Kt minor has O(t (log t)7/4) vertices.