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

2020/10/12 by Postle, Luke · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2010.05999

Abstract

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 previously showed that every graph with no K_t minor is O(t (log t)^β)-colorable for every β> 0. More specifically, they are O(t ⋅ (log log t)⁶)-colorable. In this paper, we extend that work to the list and odd generalizations of Hadwiger's conjecture.

Cited by

• Disproof of the Odd Hadwiger Conjecture
• Coloring Graphs With No Totally Odd Clique Immersion

Related

• Further progress towards Hadwiger's conjecture
• Improved bound for Hadwiger's conjecture
• Halfway to Hadwiger's Conjecture
• An even better Density Increment Theorem and its application to Hadwiger's Conjecture
• Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs