# Article

**Keywords:**

neighbor-distinguishing coloring; set coloring; neighborhood color set

**Summary:**

For a nontrivial connected graph $G$, let $c\: V(G)\to \Bbb 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 ${\rm NC}(v)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if ${\rm NC}(u)\ne {\rm 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)$. A study is made of the set chromatic number of the join $G + H$ of two graphs $G$ and $H$. Sharp lower and upper bounds are established for $\chi _s(G+H)$ in terms of $\chi _s(G)$, $\chi _s(H)$, and the clique numbers $\omega (G)$ and $\omega (H)$.

References:

[1] Chartrand, G., Okamoto, F., Rasmussen, C. W., Zhang, P.:

**The set chromatic number of a graph**. Discuss. Math. Graph Theory (to appear).

MR 2642800
[2] Chartrand, G., Zhang, P.:

**Chromatic Graph Theory**. Chapman & Hall/CRC Press Boca Raton (2008).

MR 2450569