An improved bound for the strong chromatic number

被引：18

作者：

Haxell, P. E. ^{[1
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

来源：

JOURNAL OF GRAPH THEORY | 2008年 / 58卷 / 02期

关键词：

strong chromatic number; maximum degree; partition;

D O I：

10.1002/jgt.20300

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let eta > 0 be given. Then there exists d(0) = d(0)(eta) such that the following holds. Let G be a finite graph with maximum degree at most d >= d(0) whose vertex set is partitioned into classes of size alpha d, where alpha >= 11/4 + eta. Then there exists a proper coloring of G with alpha d colors in which each class receives all alpha d colors. (C) 2008 Wiley Periodicals, Inc.

引用

页码：148 / 158

页数：11

共 50 条

[41] A new graph parameter and a construction of larger graph without increasing radio k-chromatic number [J].

Sarkar, Ushnish ;

Adhikari, Avishek .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (04) :1365-1377

[42] Edge-face chromatic number of 2-connected plane graphs with high maximum degree [J].

Zhang Zhongfu ;

Wang Weifan ;

Li Jingwen ;

Yao Bing ;

Bu Yuehua .

ACTA MATHEMATICA SCIENTIA, 2006, 26 (03) :477-482

[43] EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE [J].

张忠辅 ;

王维凡 ;

李敬文 ;

姚兵 ;

卜月华 .

ActaMathematicaScientia, 2006, (03) :477-482

[44] A new graph parameter and a construction of larger graph without increasing radio k-chromatic number [J].

Ushnish Sarkar ;

Avishek Adhikari .

Journal of Combinatorial Optimization, 2017, 33 :1365-1377

[45] The 2-Distance Chromatic Number of Planar Graphs Without 3,4,8-Cycles [J].

Bu, Yuehua ;

Zhang, Zewei ;

Zhu, Junlei ;

Zhu, Hongguo .

BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2024, 50 (06)

[46] A tight upper bound on the (2, 1)-total labeling number of outerplanar graphs [J].

Hasunuma, Toru ;

Ishii, Toshimasa ;

Ono, Hirotaka ;

Uno, Yushi .

JOURNAL OF DISCRETE ALGORITHMS, 2012, 14 :189-206

[47] An improved upper bound on the linear 2-arboricity of planar graphs [J].

Wang, Yiqiao .

DISCRETE MATHEMATICS, 2016, 339 (01) :39-45

[48] AN IMPROVED UPPER BOUND ON THE LINEAR 2-ARBORICITY OF TOROIDAL GRAPHS [J].

Hu, Xiaoxue ;

Liu, Juan ;

Wang, Yiqiao .

JOURNAL OF APPLIED ANALYSIS AND COMPUTATION, 2022, 12 (04) :1672-1678

[49] An Improved Upper Bound on the Linear 2-arboricity of 1-planar Graphs [J].

Juan Liu ;

Yi Qiao Wang ;

Ping Wang ;

Lu Zhang ;

Wei Fan Wang .

Acta Mathematica Sinica, English Series, 2021, 37 :262-278

[50] An Improved Upper Bound on the Linear 2-arboricity of 1-planar Graphs [J].

Liu, Juan ;

Wang, Yi Qiao ;

Wang, Ping ;

Zhang, Lu ;

Wang, Wei Fan .

ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2021, 37 (02) :262-278

← 1 2 3 4 5 →