Further Progress towards the List and Odd Versions of Hadwiger's Conjecture

arXiv2010.05999MaRDI QIDQ6351122FDOQ6351122

Luke Postle

Publication date: 12 October 2020

Abstract: In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $tge1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(tsqrtlogt)$ and hence is $O(tsqrtlogt)$-colorable. Recently, Norin, Song and the author showed that every graph with no $K_t$ minor is $$-colorable for every $$, making the first improvement on the order of magnitude of the $O(tsqrtlogt)$ bound. Building on that work, we previously showed that every graph with no $K_t$ minor is $$-colorable for every $$. More specifically, they are $O(tcdot(loglogt{)}^6)$-colorable. In this paper, we extend that work to the list and odd generalizations of Hadwiger's conjecture.

This page was built for publication: Further Progress towards the List and Odd Versions of Hadwiger's Conjecture

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