The r-Hued Coloring of Complements of Cycles

Given a graph G, an r-hued coloring of G is a proper vertex coloring such that for every vertex v, the number of colors appearing in its neighborhood is at least min{dG(v), r}, where dG(v) denotes the degree of v in G.The r-hued chromatic number χr(G) is the smallest number of colors needed for an r-hued coloring of G.In this paper, we study the r-hued coloring of complements of cycles.For any positive integer r, we completely determine the r-hued chromatic number of Cn by constructing explicit coloring schemes and analyzing the sizes of independent sets of color classes.