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.
@article{bwmeta1.element.doi-10_7151_dmgt_1679,
author = {Jean-S\'ebastien Sereni and Zelealem B. Yilma},
title = {A Tight Bound on the Set Chromatic Number},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {461-465},
zbl = {1293.05124},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1679}
}
Jean-Sébastien Sereni; Zelealem B. Yilma. A Tight Bound on the Set Chromatic Number. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 461-465. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1679/
[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[Crossref] | Zbl 1193.05073
[2] G. Chartrand, F. Okamoto, and P. Zhang, Neighbor-distinguishing vertex colorings of graphs, J. Combin. Math. Combin. Comput. 74 (2010) 223-251. | Zbl 1223.05066
[3] R. Gera, F. Okamoto, C. Rasmussen, and P. Zhang, Set colorings in perfect graphs, Math. Bohem. 136 (2011) 61-68. | Zbl 1224.05171