ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 33(2) (2013) 461-465
DOI: 10.7151/dmgt.1679

A Tight Bound on the Set Chromatic Number

Jean-Sébastien Sereni

LORIA, Université Diderot
Nancy, France

Zelealem B. Yilma

Department of Mathematics
Addis Ababa University
Addis Ababa, Ethiopia


We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χs(G) ≥ ⎡log2 χ(G) ⎤+ 1, where χs(G) and χ(G) are the set chromatic number and the chromatic number of G, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.

Keywords: chromatic number, set coloring, set chromatic number, neighbor, distinguishing coloring

2010 Mathematics Subject Classification: 05C15.


[1]G. Chartrand, F. Okamoto, C.W. Rasmussen, and P. Zhang, The set chromatic number of a graph, Discuss. Math. Graph Theory 29 (2009) 545--561, doi: 10.7151/dmgt.1463.
[2]G. Chartrand, F. Okamoto, and P. Zhang, Neighbor-distinguishing vertex colorings of graphs, J. Combin. Math. Combin. Comput. 74 (2010) 223--251.
[3]R. Gera, F. Okamoto, C. Rasmussen, and P. Zhang, Set colorings in perfect graphs, Math. Bohem. 136 (2011) 61--68.

Received 28 February 2012
Accepted 5 June 2012