×

List-coloring claw-free graphs with small clique number. (English) Zbl 1298.05115

Summary: M. Chudnovsky and P. Seymour [J. Comb. Theory, Ser. B 100, No. 6, 560–572 (2010; Zbl 1207.05050)] 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 1207.05050
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai M., Komlós J., Szemerédi E.: A note on Ramsey numbers. J. Combin. Theory Ser. A 29, 354-360 (1980) · Zbl 0455.05045 · doi:10.1016/0097-3165(80)90030-8
[2] Chudnovsky M., Seymour P.: Claw-free graphs VI. Coloring claw-free graphs. J. Combin. Theory Ser. B 100, 560-572 (2010) · Zbl 1207.05050 · doi:10.1016/j.jctb.2010.04.005
[3] Erdős P., Rubin A.L., Taylor H.: Choosability in graphs. Congr. Numer. 26, 125-157 (1979)
[4] Gravier S., Maffray F.: On the choice number of claw-free perfect graphs. Discrete Math. 276, 211-218 (2004) · Zbl 1031.05055 · doi:10.1016/S0012-365X(03)00292-9
[5] Greenwood R.E., Gleason A.M.: Combinatorial relations and chromatic graphs. Can. J. Math. 7, 1-7 (1955) · Zbl 0064.17901 · doi:10.4153/CJM-1955-001-4
[6] Gyárfás A.: Problems from the world surrounding perfect graphs. Zastosowania Matematyki (Applicationes Mathematicae) XIX, 413-441 (1985) · Zbl 0718.05041
[7] Kéry, G.: On a theorem of Ramsey (in Hungarian). Mat. Lapok 15, 204-224 (1964) · Zbl 0125.40502
[8] Kim J.H.: The Ramsey number R(3, t) has order of magnitude t2/log t. Random Struct. Algorithms 7, 173-207 (1995) · Zbl 0832.05084 · doi:10.1002/rsa.3240070302
[9] King, A.: Claw-free graphs and two conjectures on omega, Delta, and chi. PhD thesis, School of Computer Science, McGill University, Montreal, Canada, October 2009
[10] Radziszowski, S.: Small Ramsey numbers. Dynamic Survey #1. Electron. J. Combin (2009) · Zbl 0064.17901
[11] Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. (2) 30, 264-286 (1930) · JFM 55.0032.04
[12] Reed, B.A.: ω, Δ and χ. J. Graph Theory 27, 177-212 (1998) · Zbl 0980.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.