# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

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