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 and several bounds are established for the set chromatic number of a graph in terms of other graphical parameters.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1463,
author = {Gary Chartrand and Futaba Okamoto and Craig W. Rasmussen and Ping Zhang},
title = {The set chromatic number of a graph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {29},
year = {2009},
pages = {545-561},
zbl = {1193.05073},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1463}
}
Gary Chartrand; Futaba Okamoto; Craig W. Rasmussen; Ping Zhang. The set chromatic number of a graph. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 545-561. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1463/
[000] [1] P.N. Balister, E. Gyori, J. Lehel and R.H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math. 21 (2007) 237-250, doi: 10.1137/S0895480102414107. | Zbl 1189.05056
[001] [2] A.C. Burris and R.H. Schelp, Vertex-distinguishing proper edge colorings, J. Graph Theory 26 (1997) 73-82, doi: 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C | Zbl 0886.05068
[002] [3] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, Boca Raton, 2008), doi: 10.1201/9781584888017.
[003] [4] F. Harary and M. Plantholt, The point-distinguishing chromatic index, Graphs and Applications (Wiley, New York, 1985) 147-162.