The Erdős-Hajnal Conjecture for Long Holes and Anti-holes

2014/08/08 by Marthe Bonamy, Nicolás Bousquet, Bonamy, Marthe +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · doi:10.48550/arxiv.1408.1964

openalex publication_date 2014/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Erdős and Hajnal conjectured that, for every graph H, there exists a constant c_H such that every graph G on n vertices which does not contain any induced copy of H has a clique or a stable set of size n^c_H. We prove that for every k, there exists c_k>0 such that every graph G on n vertices not inducing a cycle of length at least k nor its complement contains a clique or a stable set of size n^c_k.

Related

• Erdos-Hajnal for graphs with no 5-hole
• Holes with hats and Erdős-Hajnal
• Excluding hooks and their complements
• Pure pairs. I. Trees and linear anticomplete pairs
• Induced subgraph density. V. All paths approach Erdos-Hajnal