List colorings of K5K_5-minor-free graphs with special list assignments

preprint2011arXivOpen access

Abstract

A {\it list assignment} LL of a graph GG is a function that assigns a set (list) L(v)L(v) of colors to every vertex vv of GG. Graph GG is called {\it LL-list colorable} if it admits a vertex coloring ϕϕ such that ϕ(v)∈L(v)ϕ(v)\in L(v) for all v∈V(G)v\in V(G) and ϕ(v)≠ϕ(w)ϕ(v)\not=ϕ(w) for all vw∈E(G)vw\in E(G). The following question was raised by Bruce Richter. Let GG be a planar, 3-connected graph that is not a complete graph. Denoting by d(v)d(v) the degree of vertex vv, is GG LL-list colorable for every list assignment LL with ∣L(v)∣=min⁡{d(v),6}|L(v)|=\min \{d(v), 6\} for all v∈V(G)v\in V(G)? More generally, we ask for which pairs (r,k)(r,k) the following question has an affirmative answer. Let rr and kk be integers and let GG be a K5K_5-minor-free rr-connected graph that is not a Gallai tree (i.e., at least one block of GG is neither a complete graph nor an odd cycle). Is GG LL-list colorable for every list assignment LL with ∣L(v)∣=min⁡{d(v),k}|L(v)|=\min\{d(v),k\} for all v∈V(G)v\in V(G)? We investigate this question by considering the components of G[Sk]G[S_k], where Sk:={v∈V(G)∣d(v)<k}S_k:=\{v\in V(G) | d(v)<k\} is the set of vertices with small degree in GG. We are especially interested in the minimum distance d(Sk)d(S_k) in GG between the components of G[Sk]G[S_k].

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.