PDF

Discussiones Mathematicae Graph Theory 29(3) (2009) 545-561
DOI: https://doi.org/10.7151/dmgt.1463

THE SET CHROMATIC NUMBER OF A GRAPH

Gary Chartrand Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA

Futaba Okamoto Mathematics Department University of Wisconsin - La Crosse La Crosse, WI 54601, USA

Craig W. Rasmussen Department of Applied Mathematics Naval Postgradute School Monterey, CA 93943, USA

Ping Zhang Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA

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 χ_s(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.

Keywords: neighbor-distinguishing coloring, set coloring, neighborhood color set.

2000 Mathematics Subject Classification: 05C15.

References

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

Received 4 April 2008
Revised 9 October 2008
Accepted 13 October 2008