کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654378 1632829 2008 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Coloring squares of planar graphs with girth six
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Coloring squares of planar graphs with girth six
چکیده انگلیسی

Wang and Lih conjectured that for every g≥5g≥5, there exists a number M(g)M(g) such that the square of a planar graph GG of girth at least gg and maximum degree Δ≥M(g)Δ≥M(g) is (Δ+1)(Δ+1)-colorable. The conjecture is known to be true for g≥7g≥7 but false for g∈{5,6}g∈{5,6}. We show that the conjecture for g=6g=6 is off by just one, i.e., the square of a planar graph GG of girth at least six and sufficiently large maximum degree is (Δ+2)(Δ+2)-colorable.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 29, Issue 4, May 2008, Pages 838–849
نویسندگان
, , , ,