کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871661 | 1440188 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Dynamic coloring parameters for graphs with given genus
ترجمه فارسی عنوان
پارامترهای رنگ آمیزی دینامیک برای نمودار با داده شده با جنس
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A proper vertex coloring of a graph G is r-dynamic if for each vâV(G), at least min{r,d(v)} colors appear in NG(v). In this paper we investigate r-dynamic versions of coloring, list coloring, and paintability. We prove that planar and toroidal graphs are 3-dynamically 10-colorable, and this bound is sharp for toroidal graphs. We also give bounds on the minimum number of colors needed for any r in terms of the genus of the graph: for sufficiently large r, every graph with genus g is r-dynamically ((r+1)(g+5)+3)-colorable when gâ¤2 and r-dynamically ((r+1)(2g+2)+3)-colorable when gâ¥3. Furthermore, each of these upper bounds for r-dynamic k-colorability also holds for r-dynamic k-choosability and for r-dynamic k-paintability.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 235, 30 January 2018, Pages 129-141
Journal: Discrete Applied Mathematics - Volume 235, 30 January 2018, Pages 129-141
نویسندگان
Sarah Loeb, Thomas Mahoney, Benjamin Reiniger, Jennifer Wise,