Back to Search Start Over

List-coloring graphs without -minors

Authors :
Kawarabayashi, Ken-ichi
Source :
Discrete Applied Mathematics. Feb2009, Vol. 157 Issue 4, p659-662. 4p.
Publication Year :
2009

Abstract

Abstract: In this note, it is shown that every graph with no -minor is -list-colorable. We also give an extremal function for the existence for a -minor. Our proof implies that there is a linear time algorithm for showing that either has a -minor or is -choosable. In fact, if the latter holds, then the algorithm gives rise to a -list-coloring. [Copyright &y& Elsevier]

Details

Language :
English
ISSN :
0166218X
Volume :
157
Issue :
4
Database :
Academic Search Index
Journal :
Discrete Applied Mathematics
Publication Type :
Academic Journal
Accession number :
36475082
Full Text :
https://doi.org/10.1016/j.dam.2008.08.015