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

[BIBTex] [PDF] [PS]


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


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.


[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