List Colorings of K 5 ‐Minor‐Free Graphs With Special List Assignments

The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d ( v ) the degree of vertex v , is G L ‐list colorable for every list assignment L with | L ( v )| = min{ d ( v ), 6} for all v ∈ V ( G )? More generally, we ask for which pairs ( r, k ) the following question has an affirmative answer. Let r and k be the integers and let G be a K 5 ‐minor‐free r ‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L ‐list colorable for every list assignment L with | L ( v )| = min{ d ( v ), k } for all v ∈ V ( G )? We investigate this question by considering the components of G [ S k ], where S k : = { v ∈ V ( G )| d ( v )8 k } is the set of vertices with small degree in G . We are especially interested in the minimum distance d ( S k ) in G between the components of G [ S k ]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012