Halfway to Hadwiger's Conjecture
share
In 1943, Hadwiger conjectured that every K_t-minor-free graph 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. Very recently, Norin and Song proved that every graph with no K_t minor is O(t(log t)^0.354)-colorable. Improving on the second part of their argument, we prove that every graph with no K_t minor is O(t(log t)^β)-colorable for every β > 1/4.
READ FULL TEXT