Advanced Search

For a nontrivial connected graph $G$, let $c:V\left(G\right)\to \mathbb{N}$ be a vertex coloring of $G$ where adjacent vertices may be colored the same. For a vertex $v\in V\left(G\right)$, the neighborhood color set $\mathrm{NC}\left(v\right)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if $\mathrm{NC}\left(u\right)\ne \mathrm{NC}\left(v\right)$ 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 }_{\mathrm{s}}\left(G\right)$. We show that the decision variant of determining ${\chi }_{\mathrm{s}}\left(G\right)$ is NP-complete in the general case, and show that ${\chi }_{\mathrm{s}}\left(G\right)$ can be...

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 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 χₛ(G) of G. The set chromatic numbers of some well-known classes of graphs are determined...

For a nontrivial connected graph $G$, let $cV\left(G\right)\to \mathbb{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 $\mathrm{NC}\left(v\right)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if $\mathrm{NC}\left(u\right)\ne \mathrm{NC}\left(v\right)$ 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\left(G\right)$. 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...