List Colorings of K5-Minor-Free Graphs With Special List Assignments
✍ Scribed by Daniel W. Cranston; Anja Pruchnewski; Zsolt Tuza; Margit Voigt
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 201 KB
- Volume
- 71
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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)<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