Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
neighbor-distinguishing coloring; set coloring; neighborhood color set
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
Search
Partner of
