| Title:
|
Set vertex colorings and joins of graphs (English) |
| Author:
|
Okamoto, Futaba |
| Author:
|
Rasmussen, Craig W. |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
59 |
| Issue:
|
4 |
| Year:
|
2009 |
| Pages:
|
929-941 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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)$. (English) |
| Keyword:
|
neighbor-distinguishing coloring |
| Keyword:
|
set coloring |
| Keyword:
|
neighborhood color set |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 1224.05184 |
| idMR:
|
MR2563567 |
| . |
| Date available:
|
2010-07-20T15:49:06Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140526 |
| . |
| Reference:
|
[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 |
| Reference:
|
[2] Chartrand, G., Zhang, P.: Chromatic Graph Theory.Chapman & Hall/CRC Press Boca Raton (2008). MR 2450569 |
| . |
