# The set chromatic number of a graph

• Volume: 29, Issue: 3, page 545-561
• ISSN: 2083-5892

top

## Abstract

top
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.

## How to cite

top

Gary Chartrand, et al. "The set chromatic number of a graph." Discussiones Mathematicae Graph Theory 29.3 (2009): 545-561. <http://eudml.org/doc/270852>.

@article{GaryChartrand2009,
abstract = {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.},
author = {Gary Chartrand, Futaba Okamoto, Craig W. Rasmussen, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {neighbor-distinguishing coloring; set coloring; neighborhood color set},
language = {eng},
number = {3},
pages = {545-561},
title = {The set chromatic number of a graph},
url = {http://eudml.org/doc/270852},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Gary Chartrand
AU - Futaba Okamoto
AU - Craig W. Rasmussen
AU - Ping Zhang
TI - The set chromatic number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 545
EP - 561
AB - 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.
LA - eng
KW - neighbor-distinguishing coloring; set coloring; neighborhood color set
UR - http://eudml.org/doc/270852
ER -

## References

top
1. [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. Zbl1189.05056
2. [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 Zbl0886.05068
3. [3] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, Boca Raton, 2008), doi: 10.1201/9781584888017.
4. [4] F. Harary and M. Plantholt, The point-distinguishing chromatic index, Graphs and Applications (Wiley, New York, 1985) 147-162.

top

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.