List Colorings of K5-Minor-Free Graphs With Special List Assignments

作者：Cranston Daniel W^*; Pruchnewski Anja; Tuza Zsolt; Voigt Margit

来源：Journal of Graph Theory, 2012, 71(1): 18-30.

DOI：10.1002/jgt.20628

• list coloring
• graph coloring
• k5-minor-free
• planar

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 vertical bar L(v)vertical bar = min{d(v), 6} for all v epsilon 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 K5-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 vertical bar L(v)vertical bar = min{d(v), k} for all v?V(G)? We investigate this question by considering the components of G[Sk], where Sk: = {v epsilon V(G)vertical bar d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(Sk) in G between the components of G[Sk].

• 出版日期2012-9