View PDF HTML (experimental)

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 $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 this https URL.
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.

Submission history

From: Shenwei Huang [view email]
[v1] Thu, 4 Jun 2026 15:01:38 UTC (22 KB)
[v2] Mon, 8 Jun 2026 13:45:28 UTC (25 KB)
[v3] Mon, 31 Aug 2026 01:49:44 UTC (26 KB)