Article ID Journal Published Year Pages File Type
419740 Discrete Applied Mathematics 2009 4 Pages PDF
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
,