For a nontrivial connected graph G, let c : V (G) → N be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v ∈ V (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) 6= 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). We show that the decision variant of determining χs(G) is NP-complete in the general case, and show that χs(G) can be efficiently calculated when G is a threshold graph. We study the difference χ(G) − χs(G), presenting new bounds that are sharp for all graphs G satisfying χ(G) = ω(G). We finally present results of the Nordhaus-Gaddum type, giving sharp bounds on the sum and product of χs(G) and χs(G).
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)$.