کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334294 | 690361 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Group coloring is Î 2P-complete
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Group coloring is Î 2P-complete Group coloring is Î 2P-complete](/preview/png/10334294.png)
چکیده انگلیسی
The group chromatic number of a graph G is the smallest integer k such that for every Abelian group A of order at least k, every orientation of G and every edge-labeling Ï:E(G)âA, there exists a vertex-coloring c:V(G)âA with c(v)-c(u)â Ï(uv) for each oriented edge uv of G. We show that the decision problem whether a given graph has group chromatic number at most k is Î 2P-complete for each integer k⩾3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 99-111
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 99-111
نویسندگان
Daniel Král',