کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872333 681740 2014 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Precoloring extension involving pairs of vertices of small distance
ترجمه فارسی عنوان
پسوند پیش رنگی شامل جفتهای رأس دور کوچک است
کلمات کلیدی
رنگ آمیزی پیش رنگ کردن، فاصله،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we consider coloring of graphs under the assumption that some vertices are already colored. Let G be an r-colorable graph and let P⊂V(G). Albertson (1998) has proved that if every pair of vertices in P has distance at least four, then every (r+1)-coloring of G[P] can be extended to an (r+1)-coloring of G, where G[P] is the subgraph of G induced by P. In this paper, we allow P to have pairs of vertices of distance at most three, and investigate how the number of such pairs affects the number of colors we need to extend the coloring of G[P]. We also study the effect of pairs of vertices of distance at most two, and extend the result by Albertson and Moore (1999).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 166, 31 March 2014, Pages 170-177
نویسندگان
, , ,