List colorings of $K_5$-minor-free graphs with special list assignments

Abstract

A {\it list assignment} $L$ of a graph $G$ is a function that assigns a set (list) $L(v)$ of colors to every vertex $v$ of $G$. Graph $G$ is called {\it $L$-list colorable} if it admits a vertex coloring $\varphi$ such that $\varphi (v)\in L(v)$ for all $v\in V(G)$ and $\varphi (v)\ne \varphi (w)$ for all $vw\in E(G)$. 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\in V(G)$? More generally, we ask for which pairs $(r,k)$ the following question has an affirmative answer. Let $r$ and $k$ be 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\in V(G)$? We investigate this question by considering the components of $G[S_k]$, where $S_k:=\{v\in 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]$.

14 pages, 2 figures, 2 tables