# The set chromatic number of a graph

Gary Chartrand; Futaba Okamoto; Craig W. Rasmussen; Ping Zhang

Discussiones Mathematicae Graph Theory (2009)

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

## Access Full Article

top## Abstract

top## How to cite

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

## Citations in EuDML Documents

top## NotesEmbed ?

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