کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649465 | 1342457 | 2009 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Linear coloring of planar graphs with large girth
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A proper vertex coloring of a graph GG is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph GG is the smallest number of colors in a linear coloring of GG. In this paper we prove that every planar graph GG with girth gg and maximum degree ΔΔ has lc(G)=⌈Δ2⌉+1 if GG satisfies one of the following four conditions: (1) g≥13g≥13 and Δ≥3Δ≥3; (2) g≥11g≥11 and Δ≥5Δ≥5; (3) g≥9g≥9 and Δ≥7Δ≥7; (4) g≥7g≥7 and Δ≥13Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 18, 28 September 2009, Pages 5678–5686
Journal: Discrete Mathematics - Volume 309, Issue 18, 28 September 2009, Pages 5678–5686
نویسندگان
André Raspaud, Weifan Wang,