List-coloring graphs without K4,k K 4 , k -minors
In this note, it is shown that every graph with no K4,k K 4 , k -minor is 4k 4 k -list-colorable. We also give an extremal function for the existence for a K4,k K 4 , k -minor. Our proof implies that there is a linear time algorithm for showing that either G G has a K4,k K 4 , k -minor or G G is 4k 4 k -choosable. In fact, if the latter holds, then the algorithm gives rise to a 4k 4 k -list-coloring.
list-coloring hadwigers conjecture