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
CNRS LORIA, Université Diderot Nancy, France | Zelealem B. Yilma
Department of Mathematics Addis Ababa University Addis Ababa, Ethiopia |

## 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) ≥ ⎡log_{2} χ(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.

## References

[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