کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653414 1632770 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graphs of girth at least 7 have high b-chromatic number
ترجمه فارسی عنوان
نمودارهایی که حداقل 7 قطر دارند، دارای تعداد بالایی از رنگ های کروماتیک هستند
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
نویسندگان
, , ,