کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950770 | 1441032 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
NP-completeness of local colorings of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A local k-coloring of a graph G is a function f:V(G)â{1,2,â¯,k} such that for each SâV(G), 2â¤|S|â¤3, there exist u,vâS with |f(u)âf(v)| at least the size of the subgraph induced by S. The local chromatic number of G is Ïâ(G)=minâ¡{k:G has a local k-coloring}. In this paper, we show that it is NP-complete to determine whether a graph has a local k-coloring for fixed k=4 or k=2tâ1, where tâ¥3. In particular, it is NP-complete to determine whether a planar graph has a local 5-coloring even restricted to the maximum degree Î=7 or 8.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 130, February 2018, Pages 25-29
Journal: Information Processing Letters - Volume 130, February 2018, Pages 25-29
نویسندگان
Zepeng Li, Enqiang Zhu, Zehui Shao, Jin Xu,