کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429036 | 687010 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graphs with maximum degree 6 are acyclically 11-colorable
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
An acyclic k-coloring of a graph G is a proper vertex coloring of G, which uses at most k colors, such that the graph induced by the union of every two color classes is a forest. In this note, we prove that every graph with maximum degree six is acyclically 11-colorable, thus improving the main result of Yadav et al. (2009) [11].
► In this paper we need to prove the existence of a certain kind of spanning trees in regular graphs.
► A good spanning tree of a Δ regular graph G is a spanning tree T such that T contains a vertex adjacent to Δ−1Δ−1 leaves.
► We then use such good spanning trees to prove our main result on acyclic colorings.
► Every graph with maximum degree 6 is acyclically 11-colorable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 15, 15 August 2011, Pages 748–753
Journal: Information Processing Letters - Volume 111, Issue 15, 15 August 2011, Pages 748–753
نویسندگان
Hervé Hocquard,