Precoloring extension for K 4 ‐minor‐free graphs

Let G =( V, E ) be a graph where every vertex v ∈ 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, …, k } for all v ∈ V then a corresponding list coloring is nothing other than an ordinary k ‐coloring of G . Assume that W ⊆ V is a subset of V such that G [ W ] is bipartite and each component of G [ W ] is precolored with two colors taken from a set of four. 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 )≥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 10. 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 ∈ V \ W and d ( W )≥7. In both cases the bound for d ( W ) is best possible. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 284‐294, 2009