کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331906 | 686963 | 2015 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on local coloring 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}. Chartrand et al. [2] asked: does there exist a graph Gk such that Ïâ(Gk)=Ï(Gk)=k? Furthermore, they conjectured that for every positive integer k, there exists a graph Gk with Ïâ(G)=k such that every local k-coloring of Gk uses all of the colors 1,2,â¯,k. In this paper we give a affirmative answer to the problem and confirm the conjecture.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 302-305
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 302-305
نویسندگان
Zepeng Li, Zehui Shao, Enqiang Zhu, Jin Xu,