Improved bound for Hadwiger's conjecture

2021/08/20 by Wang, Yan · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2108.09230

Abstract

Hadwiger conjectured in 1943 that for every integer t ≥ 1, every graph with no K_t minor is (t-1)-colorable. Kostochka, and independently Thomason, proved every graph with no K_t minor is O(t(log t)^1/2)-colorable. Recently, Postle improved it to O(t (log log t)⁶)-colorable. In this paper, we show that every graph with no K_t minor is O(t (log log t)⁵)-colorable.

Cited by

• Disproof of the Odd Hadwiger Conjecture

Related

• Further progress towards Hadwiger's conjecture
• Further Progress towards the List and Odd Versions of Hadwiger's Conjecture
• Halfway to Hadwiger's Conjecture
• Asymptotic Equivalence of Hadwiger's Conjecture and its Odd Minor-Variant
• An even better Density Increment Theorem and its application to Hadwiger's Conjecture