The list chromatic number of graphs with small clique number

被引：39

作者：

Molloy, Michael ^{[1
]}

机构：

[1] Univ Toronto, Dept Comp Sci, Toronto, ON, Canada

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2019年 / 134卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

List colouring; Local lemma; Entropy compression; INDEPENDENCE NUMBER; SPARSE;

D O I：

10.1016/j.jctb.2018.06.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that every triangle-free graph with maximum degree A has list chromatic number at most (1 + o(1))Delta/ln Delta. This matches the best-known upper bound for graphs of girth at least 5. We also provide a new proof that for any r >= 4 every K-r-free graph has list-chromatic number at most 200r Delta ln ln Delta/ln Delta. (C) 2018 Elsevier Inc. All rights reserved.

引用

页码：264 / 284

页数：21

共 50 条

[31] Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs
Nikoletseas, Sotiris
Raptopoulos, Christoforos
Spirakis, Paul G.
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2012, 2012, 7464 : 728 - 739
[32] GRAPHS WITH SMALL INDEPENDENCE NUMBER MINIMIZING THE SPECTRAL RADIUS
Du, Xue
Shi, Lingsheng
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2013, 5 (03)
[33] Rank and chromatic number of a graph
Kotlov, A
JOURNAL OF GRAPH THEORY, 1997, 26 (01) : 1 - 8
[34] Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank
Wang, Long
Wong, Dein
DISCRETE APPLIED MATHEMATICS, 2014, 166 : 276 - 281
[35] On the independence number and the chromatic number of generalized preferential attachment models
Kovalenko, Kirill
DISCRETE APPLIED MATHEMATICS, 2020, 285 : 301 - 306
[36] Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number
Lucke, Felicia
Mann, Felix
COMBINATORIAL ALGORITHMS (IWOCA 2022), 2022, 13270 : 412 - 424
[37] Upper bounds on the independence and the clique covering number
Van Nuffelen, Cyriel
Van Rompay, Kristel
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (01): : 43 - 50
[38] Upper bounds on the independence and the clique covering number
Cyriel Van Nuffelen
Kristel Van Rompay
Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2003, 1 : 43 - 50
[39] Zero-divisor Graphs of Small Upper Irredundance Number
Louartiti, Khalid
BOLETIM SOCIEDADE PARANAENSE DE MATEMATICA, 2022, 40
[40] Regular graphs with equal matching number and independence number
Yang, Zixuan
Lu, Hongliang
DISCRETE APPLIED MATHEMATICS, 2022, 310 : 86 - 90

← 1 2 3 4 5 →