The list chromatic number of graphs with small clique number

被引：37
|
作者：
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 条
  • [1] Fractional chromatic number and circular chromatic number for distance graphs with large clique size
    Liu, DDF
    Zhu, XD
    JOURNAL OF GRAPH THEORY, 2004, 47 (02) : 129 - 146
  • [2] Packing chromatic number versus chromatic and clique number
    Bresar, Bostjan
    Klavzar, Sandi
    Rall, Douglas F.
    Wash, Kirsti
    AEQUATIONES MATHEMATICAE, 2018, 92 (03) : 497 - 513
  • [3] Packing chromatic number versus chromatic and clique number
    Boštjan Brešar
    Sandi Klavžar
    Douglas F. Rall
    Kirsti Wash
    Aequationes mathematicae, 2018, 92 : 497 - 513
  • [4] Improved lower bound for the list chromatic number of graphs with no Kt minor
    Steiner, Raphael
    COMBINATORICS PROBABILITY & COMPUTING, 2022, 31 (06): : 1070 - 1075
  • [5] Normalized Laplacian eigenvalues with chromatic number and independence number of graphs
    Sun, Shaowei
    Das, Kinkar Ch
    LINEAR & MULTILINEAR ALGEBRA, 2020, 68 (01): : 63 - 80
  • [6] THE CLIQUE MINOR OF GRAPHS WITH INDEPENDENCE NUMBER TWO
    Pang, Shiyou
    Miao, Lianying
    Sun, Qingbo
    Miao, Zhengke
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2009, 1 (01) : 121 - 125
  • [7] On sufficient conditions for equality of the independence number and the clique cover number for a class of graphs
    Prosolupov, E., V
    VESTNIK SANKT-PETERBURGSKOGO UNIVERSITETA SERIYA 10 PRIKLADNAYA MATEMATIKA INFORMATIKA PROTSESSY UPRAVLENIYA, 2014, 10 (01): : 90 - 103
  • [8] Bounds for the chromatic number of graphs with partial information
    Coffman, WC
    Hakimi, SL
    Schmeichel, E
    DISCRETE MATHEMATICS, 2003, 263 (1-3) : 47 - 59
  • [9] Bounds on the Clique and the Independence Number for Certain Classes of Graphs
    Brimkov, Valentin E.
    Barneva, Reneta P.
    MATHEMATICS, 2024, 12 (02)
  • [10] On the Independence Number of Edge Chromatic Critical Graphs
    Miao Lianying
    ARS COMBINATORIA, 2011, 98 : 471 - 481
12345