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

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
نویسندگان
, ,