Precoloring Extension for K-4-Minor-Free Graphs Artikel uri icon

Open Access

  • false

Peer Reviewed

  • true

Abstract

  • Let G=(V, E) be a graph where every vertex v is an element of 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 is an element of V then a corresponding list coloring is nothing other than an ordinary k-coloring of G. Assume that W subset of 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 IN 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 vertical bar L(v)vertical bar=4 for all v is an element of V\ W and d(W)>= 7. In both cases the bound for d(W) is best possible. (C) 2009 Wiley periodicals, Inc. J Graph Theory 60: 294-294, 2009

Veröffentlichungszeitpunkt

  • Januar 4, 2009