Precoloring extension for 2-connected graphs with maximum degree three |
| |
Authors: | Margit Voigt |
| |
Affiliation: | University of Applied Sciences, Dresden, Germany |
| |
Abstract: | Let G=G(V,E) be a simple graph, L a list assignment with |L(v)|=Δ(G)∀v∈V and W⊆V an independent subset of the vertex set. Define to be the minimum distance between two vertices of W. In this paper it is shown that if G is 2-connected with Δ(G)=3 and G is not K4 then every precoloring of W is extendable to a proper list coloring of G provided that d(W)≥6. An example shows that the bound is sharp. This result completes the investigation of precoloring extensions for graphs with |L(v)|=Δ(G) for all v∈V where the precolored set W is an independent set. |
| |
Keywords: | List coloring Precoloring extension Distance constraints |
本文献已被 ScienceDirect 等数据库收录! |