An improved bound for the strong chromatic number

被引：16

作者：

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 条

[21] Ring graphs and Goldberg's bound on chromatic index [J].

Cao, Yan ;

Chen, Guantao ;

He, Shushan ;

Jing, Guangming .

JOURNAL OF GRAPH THEORY, 2020, 93 (03) :440-449

[22] A note on the adjacent vertex distinguishing total chromatic number of graphs [J].

Huang, Danjun ;

Wang, Weifan ;

Yan, Chengchao .

DISCRETE MATHEMATICS, 2012, 312 (24) :3544-3546

[23] On bounding the difference between the maximum degree and the chromatic number by a constant [J].

Weil, Vera ;

Schaudt, Oliver .

DISCRETE APPLIED MATHEMATICS, 2017, 231 :228-234

[24] The fractional chromatic number of triangle-free graphs with Δ ≤ 3 [J].

Lu, Linyuan ;

Peng, Xing .

DISCRETE MATHEMATICS, 2012, 312 (24) :3502-3516

[25] Two smaller upper bounds of list injective chromatic number [J].

Yuehua Bu ;

Kai Lu ;

Sheng Yang .

Journal of Combinatorial Optimization, 2015, 29 :373-388

[26] Total chromatic number of planar graphs with maximum degree ten [J].

Wang, Weifan .

JOURNAL OF GRAPH THEORY, 2007, 54 (02) :91-102

[27] Two smaller upper bounds of list injective chromatic number [J].

Bu, Yuehua ;

Lu, Kai ;

Yang, Sheng .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 29 (02) :373-388

[28] THE FRACTIONAL CHROMATIC NUMBER OF K\bfDelta-FREE GRAPHS [J].

Hu, Xiaolan ;

Peng, Xing .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (04) :2486-2507

[29] Vertex-connectivity, chromatic number, domination number, maximum degree and Laplacian eigenvalue distribution [J].

Wang, Long ;

Yan, Chunyu ;

Fang, Xianwen ;

Geng, Xianya ;

Tian, Fenglei .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 607 :307-318

[30] Sharp Bounds and Precise Values for the Ni-Chromatic Number of Graphs [J].

Yu, Yangfan ;

Sun, Yuefang .

JOURNAL OF INTERCONNECTION NETWORKS, 2024, 24 (04)

← 1 2 3 4 5 →