کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418397 | 681664 | 2012 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A 2-hued coloring of a graph GG is a coloring such that, for every vertex v∈V(G)v∈V(G) of degree at least 22, the neighbors of vv receive at least two colors. The smallest integer kk such that GG has a 2-hued coloring with kk colors is called the 2-hued chromatic number of GG, and is denoted by χ2(G)χ2(G). In this paper, we will show that, if GG is a regular graph, then χ2(G)−χ(G)≤2log2(α(G))+3χ2(G)−χ(G)≤2log2(α(G))+3, and, if GG is a graph and δ(G)≥2δ(G)≥2, then χ2(G)−χ(G)≤1+⌈4Δ2δ−1⌉(1+log2Δ(G)2Δ(G)−δ(G)(α(G))), and in the general case, if GG is a graph, then χ2(G)−χ(G)≤2+min{α′(G),α(G)+ω(G)2}.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2142–2146
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2142–2146
نویسندگان
A. Dehghan, A. Ahadi,