Induced subgraphs of graphs with large chromatic number. III. Long holes

2015/06/07 by Chudnovsky, Maria, Scott, Alex, Seymour, Paul · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1506.02232

Abstract

We prove a 1985 conjecture of Gyárfás that for all k,ℓ, every graph with sufficiently large chromatic number contains either a complete subgraph with k vertices or an induced cycle of length at least ℓ.

Cited by

• Optimal coloring of \cap,even hole\-free graphs with no short odd holes
• Burling graphs in graphs with large chromatic number
• Optimal binding function for (cap,even hole)-free graphs with no short odd holes

Related

• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures
• Induced subgraphs of graphs with large chromatic number. X. Holes of\n specific residue
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes