List-Coloring Claw-Free Graphs with Small Clique Number

被引：0
作者：
Louis Esperet
András Gyárfás
Frédéric Maffray
机构：
[1] CNRS/Grenoble-INP/UJF-Grenoble 1,
[2] G-SCOP (UMR5272),undefined
[3] Rényi Institute,undefined
来源：
Graphs and Combinatorics | 2014年 / 30卷
关键词：
Claw-free graphs; Chromatic number; List coloring;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight.
引用
收藏
页码：365 / 375
页数：10
相关论文
共 16 条
  • [1] Ajtai M.(1980)A note on Ramsey numbers J. Combin. Theory Ser. A 29 354-360
  • [2] Komlós J.(2010)Claw-free graphs VI. Coloring claw-free graphs J. Combin. Theory Ser. B 100 560-572
  • [3] Szemerédi E.(1979)Choosability in graphs Congr. Numer. 26 125-157
  • [4] Chudnovsky M.(2004)On the choice number of claw-free perfect graphs Discrete Math. 276 211-218
  • [5] Seymour P.(1955)Combinatorial relations and chromatic graphs Can. J. Math. 7 1-7
  • [6] Erdős P.(1985)Problems from the world surrounding perfect graphs Zastosowania Matematyki (Applicationes Mathematicae) XIX 413-441
  • [7] Rubin A.L.(1964)On a theorem of Ramsey (in Hungarian) Mat. Lapok 15 204-224
  • [8] Taylor H.(1995)The Ramsey number Random Struct. Algorithms 7 173-207
  • [9] Gravier S.(1930)(3, Proc. Lond. Math. Soc. (2) 30 264-286
  • [10] Maffray F.(undefined)) has order of magnitude undefined undefined undefined-undefined
12