2022/11/02 by Jendroľ, Stanislav, Onderko, Alfréd
#05C10 #05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2211.01041
An r-hued coloring of a simple graph G is a proper coloring of its vertices such that every vertex v is adjacent to at least min\r, °(v)\ differently colored vertices. The minimum number of colors needed for an r-hued coloring of a graph G, the r-hued chromatic number, is denoted by χr(G). In this note we show that χr(G) ≤ (r - 1)(Δ(G) + 1) + 2, for every simple graph G and every r ≥ 2, which in the case when r < Δ(G) improves the presently known Δ(G)-based upper bound on χr(G), namely r Δ(G) + 1. We also discuss the existence of graphs whose r-hued chromatic number is close to (r-1)(Δ+ 1 ) + 2 and we prove that there is a bipartite graph of maximum degree Δ whose r-hued chromatic number is (r-1)Δ+ 1 for every r ∈ \2, …, 9\ and infinitely many values of Δ≥ r + 2; we believe that (r-1)Δ(G) + 1 is the best upper bound on the r-hued chromatic number of any bipartite graph G.