کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648502 1342415 2012 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
List 2-facial 5-colorability of plane graphs with girth at least 12
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
List 2-facial 5-colorability of plane graphs with girth at least 12
چکیده انگلیسی

A proper vertex coloring of a plane graph is 2-facial if any two different vertices joined by a facial walk of length 2 are colored differently, and it is 2-distance if every two vertices at distance 2 from each other are colored differently. Note that any 2-facial coloring of a subcubic graph is 2-distance.It is known that every plane graph with girth at least 14 has a 2-facial 5-coloring [M. Montassier, A. Raspaud, A note on 2-facial coloring of plane graphs. Inform. Process. Lett. 98 (6) (2006) 235–241], and that every planar subcubic graph with girth at least 13 has a list 2-distance 5-coloring [F. Havet, Choosability of square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353–3563].We strengthen these results by proving the list 2-facial 5-colorability of plane graphs with girth at least 12.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 2, 28 January 2012, Pages 306–314
نویسندگان
, ,