Asymptotic Equivalence of Hadwiger's Conjecture and its Odd Minor-Variant
share
Hadwiger's conjecture states that every K_t-minor free graph is (t-1)-colorable. A qualitative strengthening of this conjecture raised by Gerards and Seymour, known as the Odd Hadwiger's conjecture, states similarly that every graph with no odd K_t-minor is (t-1)-colorable. For both conjectures, their asymptotic relaxations remain open, i.e., whether an upper bound on the chromatic number of the form Ct for some constant C>0 exists. We show that if every graph without a K_t-minor is f(t)-colorable, then every graph without an odd K_t-minor is 2f(t)-colorable. Using this, the recent O(tloglog t)-upper bound of Delcourt and Postle for the chromatic number of K_t-minor free graphs directly carries over to the chromatic number of odd K_t-minor-free graphs. This (slightly) improves a previous bound of O(t(loglog t)^2) for this problem by Delcourt and Postle.
READ FULL TEXT
