Article ID Journal Published Year Pages File Type
4649436 Discrete Mathematics 2009 5 Pages PDF
Abstract

Let G=G(V,E)G=G(V,E) be a simple graph, LL a list assignment with |L(v)|=Δ(G)|L(v)|=Δ(G)∀v∈V∀v∈V and W⊆VW⊆V an independent subset of the vertex set. Define d(W)≔min{d(v,w)∣v,w∈W} to be the minimum distance between two vertices of WW. In this paper it is shown that if GG is 2-connected with Δ(G)=3Δ(G)=3 and GG is not K4K4 then every precoloring of WW is extendable to a proper list coloring of GG provided that d(W)≥6d(W)≥6. An example shows that the bound is sharp. This result completes the investigation of precoloring extensions for graphs with |L(v)|=Δ(G)|L(v)|=Δ(G) for all v∈Vv∈V where the precolored set WW is an independent set.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,