Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number

摘要

A 2-hued coloring of a graph G is a coloring such that, for every vertex v∈V(G) of degree at least 2, the neighbors of v receive at least two colors. The smallest integer k such that G has a 2-hued coloring with k colors is called the 2-hued chromatic number of G, and is denoted by ~(χ2)(G). In this paper, we will show that, if G is a regular graph, then ~(χ2)(G)-χ(G)≤2log _2(α(G))+3, and, if G is a graph and δ(G)<2, then ~(χ2)(G)-χ(G)≤1+4 ~(Δ2)δ-1?(1+log _(2Δ(G)2Δ(G)-δ(G))(α(G))), and in the general case, if G is a graph, then ~(χ2)(G)-χ(G)≤2+min ~α′(G),α(G)+ω(G)2.