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 条

[31] Upper bounds on adjacent vertex distinguishing total chromatic number of graphs [J].

Hu, Xiaolan ;

Zhang, Yunqing ;

Miao, Zhengke .

DISCRETE APPLIED MATHEMATICS, 2017, 233 :29-32

[32] The entire chromatic number of graphs embedded on the torus with large maximum degree [J].

Hu, Xiaoxue ;

Wang, Ping ;

Wang, Yiqiao ;

Wang, Weifan .

THEORETICAL COMPUTER SCIENCE, 2017, 689 :108-116

[33] Upper Bounds on the Chromatic Polynomial of a Connected Graph with Fixed Clique Number [J].

Long, Shude ;

Ren, Han .

GRAPHS AND COMBINATORICS, 2023, 39 (03)

[34] Upper Bounds on the Chromatic Polynomial of a Connected Graph with Fixed Clique Number [J].

Shude Long ;

Han Ren .

Graphs and Combinatorics, 2023, 39

[35] The chromatic number of the square of a Halin graph with maximum degree five is six [J].

Wang, Yiqiao ;

Hu, Xiaoxue ;

Wang, Weifan .

ARS COMBINATORIA, 2017, 133 :217-231

[36] Partition graphs of independence number 2 into two subgraphs with large chromatic numbers [J].

Wang, Yue ;

Yu, Gexin .

DISCRETE MATHEMATICS, 2022, 345 (04)

[37] Improved lower bound on the energy of line graphs [J].

Akbari, Saieed ;

Lin, Hongying .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2023, 674 :442-452

[38] Improved Upper Bounds on the Crossing Number [J].

Dujmovic, Vida ;

Kawarabayashi, Ken-ichi ;

Mohar, Bojan ;

Wood, David R. .

PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SGG'08), 2008, :375-384

[39] Variable neighborhood search for extremal graphs. 23. On the Randic index and the chromatic number [J].

Hansen, Pierre ;

Vukicevic, Damir .

DISCRETE MATHEMATICS, 2009, 309 (13) :4228-4234

[40] Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem [J].

Jenssen, Matthew ;

Patel, Viresh ;

Regts, Guus .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 169 :233-252

← 1 2 3 4 5 →