# 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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text: