Precoloring extension for K4-minor-free graphs

Pruchnewski, Anja; Voigt, Margit

Let $G=(V,E)$ be a graph where every vertex $v \in V$ is assigned a list of available colors $L(v)$. We say that $G$ is list colorable for a given list assignment if we can color every vertex using its list such that adjacent vertices get different colors. If $L(v)=\{1,\dots,k\}$ for all $v\in V$ then a corresponding list coloring is nothing other than an ordinary $k$-coloring of $G$. Assume that $W\subseteq V$ is a subset of $V$ such that $G[W]$ is bipartite and each component of $G[W]$ is precolored with two colors. The minimum distance between the components of $G[W]$ is denoted by $d(W)$. We will show that if $G$ is $K_4$-minor-free and $d(W)\geq 7$, then such a precoloring of $W$ can be extended to a 4-coloring of all of $V$. This result clarifies a question posed in \cite{HM}. Moreover, we will show that such a precoloring is extendable to a list coloring of $G$ for outerplanar graphs, provided that $|L(v)|=4$ for all $v\in V\setminus W$ and $d(W)\geq 7$. In both cases the bound for $d(W)$ is best possible.


Citation style:
Could not load citation form.


Use and reproduction:
All rights reserved