کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649436 | 1342455 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Precoloring extension for 2-connected graphs with maximum degree three
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Precoloring extension for 2-connected graphs with maximum degree three Precoloring extension for 2-connected graphs with maximum degree three](/preview/png/4649436.png)
چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 309, Issue 15, 6 August 2009, Pages 4926–4930
نویسندگان
Margit Voigt,