کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649436 1342455 2009 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Precoloring extension for 2-connected graphs with maximum degree three
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Precoloring extension for 2-connected graphs with maximum degree three
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 15, 6 August 2009, Pages 4926–4930
نویسندگان
,