zbMATH — the first resource for mathematics

The set chromatic number of a graph. (English) Zbl 1193.05073
Summary: For a nontrivial connected graph \(G\), let \(c:V(G)\to N\) be a vertex coloring of \(G\) where adjacent vertices may be colored the same. For a vertex \(v\) of \(G\), the neighborhood color set \(\text{NC}(v)\) is the set of colors of the neighbors of \(v\). The coloring \(c\) is called a set coloring if \(\text{NC}(u)\neq \text{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 \(\chi_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.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI