کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874187 | 1441027 | 2018 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Total coloring of rooted path graphs
ترجمه فارسی عنوان
رنگ آمیزی کل مسیر ریشه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A total coloring of a graph is an assignment of colors to both its vertices and edges so that adjacent or incident elements acquire distinct colors. In this note, we give a simple greedy algorithm to totally color a rooted path graph G with at most Î(G)+2 colors, where Î(G) is the maximum vertex degree of G. Our algorithm is inspired by a method by Bojarshinov (2001) [3] for interval graphs and provides a new proof that the Total Coloring Conjecture, posed independently by Behzad (1965) [1] and Vizing (1968) [15], holds for rooted path graphs. In the process, we also prove a useful property of greedy neighborhood coloring for chordal graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 135, July 2018, Pages 73-76
Journal: Information Processing Letters - Volume 135, July 2018, Pages 73-76
نویسندگان
Martin Charles Golumbic,