Erdős-Hajnal conjecture beyond five-vertex graphs
Abstract
In 1989, Erdős and Hajnal conjectured that for any graph H, there is a constant c=c(H)>0 such that every n-vertex graph G with no induced copies of H contains a clique or an independent set of size at least nc. This conjecture, known as the Erdős-Hajnal conjecture, is a central open problem in combinatorics and listed as one of the top 10 Erdős problems by Bloom on the Erdős problem website https://www.erdosproblems.com/. In a recent breakthrough, Nguyen, Scott and Seymour proved that Erdős-Hajnal conjecture holds for the case when H is the five-vertex path, which, combined with known results, implies that Erdős-Hajnal conjecture holds for every five-vertex graph. In this paper, we extend the iterative sparsification framework recently developed by Nguyen, Scott and Seymour. We introduce a generalized niceness condition relaxing their nice condition, a novel intermediate property concerning combs and a general structural lemma (which may be of independent interest) that is sufficient to deduce the Erdős-Hajnal conjecture. This framework simultaneously recovers the recent result on the five-vertex path (PLMS 2026) and the classical result on the bull graph by Chudnovsky and Safra (JCTB 2008) as special cases, thereby unifying these two previously independent strands, and further proves the conjecture for two new cases: the E-graph (which contains the five-vertex path) and the Bird graph (which contains both the five-vertex path and the bull). These are the first two six-vertex graphs whose validity does not follow from the known operations (see Alon-Pach-Solymosi, Combinatorica 2001, and Nguyen-Scott-Seymour, TAMS 2026) that preserve the Erdős-Hajnal property.
Related
- The Erdős-Hajnal Property for the six-vertex Graph with Edge Set {ab,bc,cd,de,af,bf,df}
- Erdős-Hajnal for excluding paths
- The Erdős--Hajnal property for paths
- On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
- Equivalence between Erdős–Hajnal and polynomial Rödl and Nikiforov conjectures
BibTeX
@misc{huang2026erdőshajnal,
title = {{Erdős-Hajnal conjecture beyond five-vertex graphs}},
author = {Shenwei Huang and Yiao Ju and Yidong Zhou},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2606.06258},
eprint = {2606.06258},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.06258},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Erdős-Hajnal conjecture beyond five-vertex graphs
AU - Shenwei Huang
AU - Yiao Ju
AU - Yidong Zhou
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2606.06258
UR - https://arxiv.org/abs/2606.06258
AB - In 1989, Erdős and Hajnal conjectured that for any graph H, there is a constant c=c(H)>0 such that every n-vertex graph G with no induced copies of H contains a clique or an independent set of size at least n^c. This conjecture, known as the Erdős-Hajnal conjecture, is a central open problem in combinatorics and listed as one of the top 10 Erdős problems by Bloom on the Erdős problem website https://www.erdosproblems.com/. In a recent breakthrough, Nguyen, Scott and Seymour proved that Erdős-Hajnal conjecture holds for the case when H is the five-vertex path, which, combined with known results, implies that Erdős-Hajnal conjecture holds for every five-vertex graph. In this paper, we extend the iterative sparsification framework recently developed by Nguyen, Scott and Seymour. We introduce a generalized niceness condition relaxing their nice condition, a novel intermediate property concerning combs and a general structural lemma (which may be of independent interest) that is sufficient to deduce the Erdős-Hajnal conjecture. This framework simultaneously recovers the recent result on the five-vertex path (PLMS 2026) and the classical result on the bull graph by Chudnovsky and Safra (JCTB 2008) as special cases, thereby unifying these two previously independent strands, and further proves the conjecture for two new cases: the E-graph (which contains the five-vertex path) and the Bird graph (which contains both the five-vertex path and the bull). These are the first two six-vertex graphs whose validity does not follow from the known operations (see Alon-Pach-Solymosi, Combinatorica 2001, and Nguyen-Scott-Seymour, TAMS 2026) that preserve the Erdős-Hajnal property.
ER -