Further progress towards Hadwiger's conjecture

From MaRDI portal




Abstract: In 1943, Hadwiger conjectured that every graph with no Kt minor is (t−1)-colorable for every tge1. In the 1980s, Kostochka and Thomason independently proved that every graph with no Kt minor has average degree O(tsqrtlogt) and hence is O(tsqrtlogt)-colorable. Recently, Norin, Song and the author showed that every graph with no Kt minor is -colorable for every , making the first improvement on the order of magnitude of the O(tsqrtlogt) bound. Building on that work, we show in this paper that every graph with no Kt minor is -colorable for every . More specifically in conjunction with another paper by the author, they are O(tcdot(loglogt)18)-colorable.














This page was built for publication: Further progress towards Hadwiger's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6343382)