A Tight Bound on the Set Chromatic Number

Jean-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 -