The set chromatic number of a graph
Gary Chartrand, Futaba Okamoto, Craig W. Rasmussen, Ping Zhang · Discussiones Mathematicae Graph Theory · 2009
For a nontrivial connected graph G, let c : V (G) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number χ(s)(G) of G. The set chromatic numbers of some well-known classes of graphs are determined and several bounds are established for the set chromatic number of a graph in terms of other graphical parameters.