# A Tight Bound on the Set Chromatic Number

Jean-Sébastien Sereni; Zelealem B. Yilma

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 2, page 461-465
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJean-Sébastien Sereni, and Zelealem B. Yilma. "A Tight Bound on the Set Chromatic Number." Discussiones Mathematicae Graph Theory 33.2 (2013): 461-465. <http://eudml.org/doc/268003>.

@article{Jean2013,

abstract = {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.},

author = {Jean-Sébastien Sereni, Zelealem B. Yilma},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {chromatic number; set coloring; set chromatic number; neighbor; distinguishing coloring},

language = {eng},

number = {2},

pages = {461-465},

title = {A Tight Bound on the Set Chromatic Number},

url = {http://eudml.org/doc/268003},

volume = {33},

year = {2013},

}

TY - JOUR

AU - Jean-Sébastien Sereni

AU - Zelealem B. Yilma

TI - A Tight Bound on the Set Chromatic Number

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 2

SP - 461

EP - 465

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

LA - eng

KW - chromatic number; set coloring; set chromatic number; neighbor; distinguishing coloring

UR - http://eudml.org/doc/268003

ER -

## References

top- [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] Zbl1193.05073
- [2] G. Chartrand, F. Okamoto, and P. Zhang, Neighbor-distinguishing vertex colorings of graphs, J. Combin. Math. Combin. Comput. 74 (2010) 223-251. Zbl1223.05066
- [3] R. Gera, F. Okamoto, C. Rasmussen, and P. Zhang, Set colorings in perfect graphs, Math. Bohem. 136 (2011) 61-68. Zbl1224.05171

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.