Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419740 | Discrete Applied Mathematics | 2009 | 4 Pages |
Abstract
In this note, it is shown that every graph with no K4,kK4,k-minor is 4k4k-list-colorable. We also give an extremal function for the existence for a K4,kK4,k-minor. Our proof implies that there is a linear time algorithm for showing that either GG has a K4,kK4,k-minor or GG is 4k4k-choosable. In fact, if the latter holds, then the algorithm gives rise to a 4k4k-list-coloring.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ken-ichi Kawarabayashi,