Improved lower bound for the list chromatic number of graphs with no K-t minor
OPEN ACCESS
Loading...
Author / Producer
Date
2022-11
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Hadwiger's conjecture asserts that every graph without a K-t-minor is (t - 1)-colourable. It is known that the exact version of Hadwiger's conjecture does not extend to list colouring, but it has been conjectured by Kawarabayashi and Mohar (2007) that there exists a constant c such that every graph with no K-t-minor has list chromatic number at most ct. More specifically, they also conjectured that this holds for c = 3/2, Refuting the latter conjecture, we show that the maximum list chromatic number of graphs with no K-t-minor is at least (2 - o(1))t, and hence c >= 2 in the above conjecture is necessary. This improves the previous best lower bound by Bark, Joret and Wood (2011), who proved that c >= 4/3. Our lower-bound examples are obtained via the probabilistic method.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
31 (6)
Pages / Article No.
1070 - 1075
Publisher
Cambridge University Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
list colouring; list chromatic number; choosability; graph minors; Hadwiger's conjecture
Organisational unit
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)