کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903882 | 1632964 | 2018 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
ترجمه فارسی عنوان
رنگ آمیزی مکاتبات و کاربرد آن در گرافهای مسطح رنگی لیست بدون چرخه طول 4 تا 8
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 129, March 2018, Pages 38-54
Journal: Journal of Combinatorial Theory, Series B - Volume 129, March 2018, Pages 38-54
نویسندگان
ZdenÄk DvoÅák, Luke Postle,