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 条

[41] Cubic graphs with equal independence number and matching number
Mohr, Elena
Rautenbach, Dieter
DISCRETE MATHEMATICS, 2021, 344 (01)
[42] Treewidth versus clique number. II. Tree-independence number
Dallard, Clement
Milanic, Martin
Storgel, Kenny
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 164 : 404 - 442
[43] The Structure of Minimally 1-Tough Graphs with Small Independence Number
Cao, Shiyu
Chen, Jing
Zheng, Wei
GRAPHS AND COMBINATORICS, 2025, 41 (02)
[44] Complete immersions in graphs with independence number two and small forbidden subgraphs
Quiroz, Daniel A.
PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, 2021, 195 : 343 - 349
[45] New analytical lower bounds on the clique number of a graph
Stozhkov, Vladimir
Pastukhov, Grigory
Boginski, Vladimir
Pasiliao, Eduardo L.
OPTIMIZATION METHODS & SOFTWARE, 2017, 32 (02) : 336 - 368
[46] Estimates of the number of independent sets in graphs with a fixed independence number
Dainyak A.B.
Moscow University Computational Mathematics and Cybernetics, 2009, 33 (2) : 97 - 100
[47] On the strength and independence number of graphs
Ichishima, Rikio
Muntaner-Batle, Francesc A.
Takahashi, Yukio
CONTRIBUTIONS TO MATHEMATICS, 2022, 6 : 25 - 29
[48] Beyond Ohba's Conjecture: A bound on the choice number of k-chromatic graphs with n vertices
Noel, Jonathan A.
West, Douglas B.
Wu, Hehui
Zhu, Xuding
EUROPEAN JOURNAL OF COMBINATORICS, 2015, 43 : 295 - 305
[49] Independence number in path graphs
Knor, M
Niepel, L
COMPUTING AND INFORMATICS, 2004, 23 (02) : 179 - 187
[50] On the chromatic number of a space with two forbidden distances
A. M. Raigorodskii
Doklady Mathematics, 2006, 73 : 417 - 420

← 1 2 3 4 5 →