کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653414 | 1632770 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graphs of girth at least 7 have high b-chromatic number
ترجمه فارسی عنوان
نمودارهایی که حداقل 7 قطر دارند، دارای تعداد بالایی از رنگ های کروماتیک هستند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A b-coloring of a graph is a proper coloring of its vertices such that every color class contains a vertex that has neighbors in all other color classes. The b-chromatic number of a graph is the largest integer b(G) such that the graph has a b-coloring with b(G) colors. This metric is upper bounded by the largest integer m(G) for which G has at least m(G) vertices with degree at least m(G)â1. There are a number of results reporting that graphs with high girth have high b-chromatic number when compared to m(G). Here, we prove that every graph with girth at least 7 has b-chromatic number at least m(G)â1. Our proof also yields a polynomial algorithm that produces an optimal b-coloring of these graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 48, August 2015, Pages 154-164
Journal: European Journal of Combinatorics - Volume 48, August 2015, Pages 154-164
نویسندگان
V. Campos, C. Lima, A. Silva,