Answers are grounded in this paper and cite their sources.
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. As a direct corollary, we present a new state of the art bound O(t log log t) for the chromatic number of graphs with no odd K t -minor. Moreover, the short proof of our result substantially simplifies the proofs of all the previous asymptotic bounds for the chromatic number of odd K t -minor free graphs established in a sequence of papers during the last 12 years.
No takes yet. Share an insight, caveat, or question.
Raphael Steiner (2022) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: