Further progress towards Hadwiger's conjecture

06/21/2020

∙

by   Luke Postle, et al.

∙

0

∙

share

In 1943, Hadwiger conjectured that every graph with no K_t minor is (t-1)-colorable for every t≥ 1. In the 1980s, Kostochka and Thomason independently proved that every graph with no K_t minor has average degree O(t√(log t)) and hence is O(t√(log t))-colorable. Recently, Norin, Song and the author showed that every graph with no K_t minor is O(t(log t)^β)-colorable for every β > 1/4, making the first improvement on the order of magnitude of the O(t√(log t)) bound. Building on that work, we show in this paper that every graph with no K_t minor is O(t (log t)^β)-colorable for every β > 0. More specifically in conjunction with another paper by the author, they are O(t · (loglog t)^18)-colorable.