A TIGHT BOUND ON THE SET CHROMATIC NUMBER

被引：2

作者：

Sereni, Jean-Sebastien ^{[1
]}

Yilma, Zelealem B. ^{[2
]}

机构：

[1] Univ Diderot, LORIA, CNRS, Nancy, France

[2] Addis Ababa Univ, Dept Math, Addis Ababa, Ethiopia

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2013年 / 33卷 / 02期

关键词：

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

D O I：

10.7151/dmgt.1679

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 chi(s)(G) equal to or greater than inverted right perpendicularlog(2) chi(G)inverted left perpendicular + 1, where chi(s)(G) and chi(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.

引用

页码：461 / 465

页数：5

共 50 条

[21] Upper bound for radio k-chromatic number of graphs in connection with partition of vertex set
Saha, Laxman
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (01) : 342 - 355
[22] A bound on the chromatic number of the square of a planar graph
Molloy, M
Salavatipour, MR
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (02) : 189 - 213
[23] A new upper bound on the cyclic chromatic number
Borodin, O. V.
Broersma, H. J.
Glebov, A.
van den Heuvel, J.
JOURNAL OF GRAPH THEORY, 2007, 54 (01) : 58 - 72
[24] Using stable sets to bound the chromatic number
de Werra, D
Hansen, P
INFORMATION PROCESSING LETTERS, 2003, 87 (03) : 127 - 131
[25] An Improved Bound on the Chromatic Number of the Pancake Graphs
Konstantinova, Elena
Droogendijk, Leen
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (01) : 35 - 46
[26] New eigenvalue bound for the fractional chromatic number
Guo, Krystal
Spiro, Sam
JOURNAL OF GRAPH THEORY, 2024, 106 (01) : 167 - 181
[27] A Bound on the Chromatic Number of an Almost Planar Graph
Nenashev G.V.
Journal of Mathematical Sciences, 2014, 196 (6) : 784 - 790
[28] Reexploring the upper bound for the chromatic number of graphs
LI Shuchao 1
2. Laboratory of Nonlinear Analysis
Progress in Natural Science, 2004, (03) : 84 - 86
[29] AN UPPER BOUND FOR THE HARMONIOUS CHROMATIC NUMBER OF A GRAPH
LEE, SM
JOURNAL OF GRAPH THEORY, 1987, 11 (04) : 565 - 567
[30] A lower bound on the chromatic number of Mycielski graphs
Caramia, M
Dell'Olmo, P
DISCRETE MATHEMATICS, 2001, 235 (1-3) : 79 - 86

← 1 2 3 4 5 →