کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646609 1342307 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Facial list colourings of plane graphs
ترجمه فارسی عنوان
رنگ آمیزی لیست چهره های نمودارهای صفحه
کلمات کلیدی
رنگ آمیزی فهرست ؛ رنگ آمیزی صورت؛ کل رنگ آمیزی؛ رنگ آمیزی کل؛ نمودار صفحه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Let G=(V,E,F)G=(V,E,F) be a connected plane graph, with vertex set VV, edge set EE, and face set FF. For X∈{V,E,F,V∪E,V∪F,E∪F,V∪E∪F}X∈{V,E,F,V∪E,V∪F,E∪F,V∪E∪F}, two distinct elements of XX are facially adjacent in GG if they are incident elements, adjacent vertices, adjacent faces, or facially adjacent edges (edges that are consecutive on the boundary walk of a face of GG). A list kk-colouring is facial with respect to XX if there is a list kk-colouring of elements of XX such that facially adjacent elements of XX receive different colours. We prove that every plane graph G=(V,E,F)G=(V,E,F) has a facial list 4-colouring with respect to X=EX=E, a facial list 6-colouring with respect to X∈{V∪E,E∪F}X∈{V∪E,E∪F}, and a facial list 8-colouring with respect to X=V∪E∪FX=V∪E∪F. For plane triangulations, each of these results is improved by one and it is tight. These results complete the theorem of Thomassen that every plane graph has a (facial) list 5-colouring with respect to X∈{V,F}X∈{V,F} and the theorem of Wang and Lih that every simple plane graph has a (facial) list 7-colouring with respect to X=V∪FX=V∪F.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 11, 6 November 2016, Pages 2826–2831
نویسندگان
, , ,