کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423493 | 1342396 | 2011 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Upper bounds on the linear chromatic number of a graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a union of vertex-disjoint paths. The linear chromatic number lc(G) of G is the smallest number of colors in a linear coloring of G.Let G be a graph with maximum degree Î(G). In this paper we prove the following results: (1) lc(G)â¤12(Î(G)2+Î(G)); (2) lc(G)â¤8 if Î(G)â¤4; (3) lc(G)â¤14 if Î(G)â¤5; (4) lc(G)â¤â0.9Î(G)â+5 if G is planar and Î(G)â¥52.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 4, 28 February 2011, Pages 232-238
Journal: Discrete Mathematics - Volume 311, Issue 4, 28 February 2011, Pages 232-238
نویسندگان
Chao Li, Weifan Wang, André Raspaud,