Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant
OPEN ACCESS
Loading...
Author / Producer
Date
2022-07
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Hadwiger's conjecture states that every Kt-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 Kt-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 Kt-minor is f(t)-colorable, then every graph without an odd Kt-minor is 2f(t)-colorable. As a direct corollary, we present a new state of the art bound O(tloglogt) for the chromatic number of graphs with no odd Kt-minor. Moreover, the short proof of our result substantially simplifies the proofs of all the previous asymptotic bounds for the chromatic number of odd Kt-minor free graphs established in a sequence of papers during the last 12 years.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
155
Pages / Article No.
45 - 51
Publisher
Academic Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Graph coloring; Chromatic number; Graph minors; Odd minor; Hadwiger’s conjecture
Organisational unit
03672 - Steger, Angelika / Steger, Angelika
02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science