2023/07/12 by Tung Nguyen, Nguyen, Tung, Alex Scott +3
Computer Science · Mathematics · #05C35 #05C42 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #Graph Theory and Algorithms #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2307.06379
openalex publication_date 2023/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for every two cycles C,D, there exists c>0 such that if G is both C-free and D-free then G has a clique or stable set of size at least |G|c. ("H-free" means with no induced subgraph isomorphic to H, and D denotes the complement graph of D.) Since the five-vertex cycle C5 is isomorphic to its complement, this extends the earlier result that C5 satisfies the Erdős-Hajnal conjecture. It also unifies and strengthens several other results. The results for cycles are special cases of results for subdivisions, as follows. Let H,J be obtained from smaller graphs by subdividing every edge exactly twice. We will prove that there exists c>0 such that if G is both H-free and J-free then G has a clique or stable set of size at least |G|c. And the same holds if H and/or J is obtained from a graph bychoosing a forest F and subdividing every edge not in F at least five times. Our proof uses the framework of iterative sparsification developed in other papers of this series. Along the way, we will also give a short and simple proof of a celebrated result of Fox and Sudakov, that says that for all H, every H-free graph contains either a large stable set or a large complete bipartite subgraph.