A Tight Bound on the Set Chromatic Number

• Autorzy: Jean-Sébastien Sereni , Zelealem B. Yilma
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

chromatic number; set coloring; set chromatic number; neighbor; distinguishing coloring

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 2
• Strony: 461-465

Daty

wydano

2013-05-01

online

2013-04-13

Twórcy

autor

Jean-Sébastien Sereni

• CNRS LORIA, Université Diderot Nancy, France,

autor

Zelealem B. Yilma

• Department of Mathematics Addis Ababa University Addis Ababa, Ethiopia,

Bibliografia

• [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]
• [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.

Identyfikatory

DOI

10.7151/dmgt.1679