Set vertex colorings and joins of graphs

Okamoto, Futaba, Rasmussen, Craig W., and Zhang, Ping. "Set vertex colorings and joins of graphs." Czechoslovak Mathematical Journal 59.4 (2009): 929-941. <http://eudml.org/doc/37967>.

@article{Okamoto2009,
abstract = {For a nontrivial connected graph $G$, let $c\: V(G)\rightarrow \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 $\{\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)$.},
author = {Okamoto, Futaba, Rasmussen, Craig W., Zhang, Ping},
journal = {Czechoslovak Mathematical Journal},
keywords = {neighbor-distinguishing coloring; set coloring; neighborhood color set; neighbour-distinguishing colouring; set colouring; neighbourhood colour set},
language = {eng},
number = {4},
pages = {929-941},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Set vertex colorings and joins of graphs},
url = {http://eudml.org/doc/37967},
volume = {59},
year = {2009},
}

TY - JOUR
AU - Okamoto, Futaba
AU - Rasmussen, Craig W.
AU - Zhang, Ping
TI - Set vertex colorings and joins of graphs
JO - Czechoslovak Mathematical Journal
PY - 2009
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 59
IS - 4
SP - 929
EP - 941
AB - For a nontrivial connected graph $G$, let $c\: V(G)\rightarrow \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 ${\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)$.
LA - eng
KW - neighbor-distinguishing coloring; set coloring; neighborhood color set; neighbour-distinguishing colouring; set colouring; neighbourhood colour set
UR - http://eudml.org/doc/37967
ER -