Premium
List Colorings of K 5 ‐Minor‐Free Graphs With Special List Assignments
Author(s) -
Cranston Daniel W.,
Pruchnewski Anja,
Tuza Zsolt,
Voigt Margit
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20628
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , planar graph , discrete mathematics
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