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

Let G=(V,E,F)G=(V,E,F) be a connected, loopless, and bridgeless 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 elements xx and yy of XX are facially adjacent in GG if they are incident, or they are adjacent vertices, or adjacent faces, or facially adjacent edges (i.e. edges that are consecutive on the boundary walk of a face of GG). A kk-colouring is facial with respect to XX if there is a kk-colouring of elements of XX such that facially adjacent elements of XX receive different colours. We prove that: (i) Every plane graph G=(V,E,F)G=(V,E,F) has a facial 8-colouring with respect to X=V∪E∪FX=V∪E∪F (i.e. a facial entire 8-colouring). Moreover, there is plane graph requiring at least 7 colours in any such colouring. (ii) Every plane graph G=(V,E,F)G=(V,E,F) has a facial 6-colouring with respect to X=E∪FX=E∪F, in other words, a facial edge–face 6-colouring.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 626–631
نویسندگان
, , ,