کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777657 | 1632971 | 2017 | 42 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
5-list-coloring planar graphs with distant precolored vertices
ترجمه فارسی عنوان
نمودارهای فلاری 5 رنگی با رأس های دقت بالا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
فهرست رنگ آمیزی، پس زمینه پیش رنگ نمودارهای پلانار،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We answer positively the question of Albertson asking whether every planar graph can be 5-list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if G is a planar graph, H is a connected subgraph of G and L is an assignment of lists of colors to the vertices of G such that |L(v)|â¥5 for every vâV(G)âV(H) and G is not L-colorable, then G contains a subgraph with O(|H|2) vertices that is not L-colorable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 311-352
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 311-352
نویسندگان
ZdenÄk DvoÅák, Bernard Lidický, Bojan Mohar, Luke Postle,