کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333108 | 688299 | 2005 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
List total colorings of series-parallel graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|⩾min{5,Î+1} for each vertex v and |L(e)|⩾max{5,d(v)+1,d(w)+1} for each edge e=vw, where Î is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Î+1 colors if Î⩾4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 3, Issue 1, March 2005, Pages 47-60
Journal: Journal of Discrete Algorithms - Volume 3, Issue 1, March 2005, Pages 47-60
نویسندگان
Xiao Zhou, Yuki Matsuo, Takao Nishizeki,