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 条
12345