کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949810 | 1364257 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Upper bounds for the achromatic and coloring numbers of a graph
ترجمه فارسی عنوان
محدوده های بالا برای تعداد آروماتیک و رنگ آمیزی یک گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شماره کروماتیک، تعداد رنگ، تعداد آکروماتیک، رندی؟ فهرست مطالب،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
DvoÅák et al. introduced a variant of the RandiÄ index of a graph G, denoted by Râ²(G), where Râ²(G)=âuvâE(G)1max{d(u),d(v)}, and d(u) denotes the degree of a vertex u in G. The coloring number col(G) of a graph G is the smallest number k for which there exists a linear ordering of the vertices of G such that each vertex is preceded by fewer than k of its neighbors. It is well-known that Ï(G)â¤col(G) for any graph G, where Ï(G) denotes the chromatic number of G. In this note, we show that for any graph G without isolated vertices, col(G)â¤2Râ²(G), with equality if and only if G is obtained from identifying the center of a star with a vertex of a complete graph. This extends some known results. In addition, we present some new spectral bounds for the coloring and achromatic numbers of a graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 217, Part 2, 30 January 2017, Pages 375-380
Journal: Discrete Applied Mathematics - Volume 217, Part 2, 30 January 2017, Pages 375-380
نویسندگان
Baoyindureng Wu, Clive Elphick,