The r-Hued Coloring of Complements of Cycles

Abstract

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 { d G ( v ) , r } , where d G ( 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 C n by constructing explicit coloring schemes and analyzing the sizes of independent sets of color classes.