Open problem, Combinatorics and discrete mathematics, posed 1977

Erdős–Hajnal conjecture

OpenErdős

For every finite graph $H$ , there exists a constant $\delta_H > 0$ such that every $n$ -vertex graph $G$ not containing $H$ as an induced subgraph has either a clique or an independent set of polynomial size at least $n^{\delta_H}$ .

Posed by, 1977Paul Erdős

Research frontier as of 2026

As of 2026, the Erdős–Hajnal conjecture remains open for general forbidden graphs $H$ on $6$ or more vertices (such as $P_6$ and $C_6$ ). For arbitrary $H$ , the best known universal lower bound on the largest homogeneous set in an $H$ -free $n$ -vertex graph is $2^{c_H \sqrt{\log n \log\log n}}$ (Bucić, Nguyen, Scott, and Seymour, 2023). On the structural side, the series Induced subgraph density by Nguyen, Scott, and Seymour resolved the conjecture for $P_5$ -free graphs—completing all graphs on at most $5$ vertices—and proved that hereditary graph classes of bounded VC-dimension satisfy the polynomial Erdős–Hajnal property.

Best known results

For every graph $H$ , every $H$ -free $n$ -vertex graph has a clique or independent set of size at least $2^{c_H \sqrt{\log n \log\log n}}$ (Bucić, Nguyen, Scott, and Seymour, 2023).
The full polynomial conjecture holds for all graphs $H$ with $|V(H)| \le 5$ (culminating in $C_5$ by Chudnovsky–Scott–Seymour–Spirkl 2021 and $P_5$ by Nguyen–Scott–Seymour 2023) and all graphs obtained from them by vertex substitution.

Tools and where they stop

Tool	Achieved	Where it stops
Rödl's theorem and iterative density-increment / blockade decomposition	Uses Rödl's theorem (that $H$ -free graphs contain linear-sized $\varepsilon$ -restricted subsets) together with balanced blockades of subgraphs to prove the $2^{c_H \sqrt{\log n \log\log n}}$ bound and resolve $P_5$ and bounded VC-dimension.	For general $H$ whose closures can have unbounded VC-dimension, density increments shrink the vertex set by quasi-polynomial factors across stages unless a structural split can be maintained at polynomial scale.

Open questions

Does the Erdős–Hajnal conjecture hold for $P_6$ -free graphs and $C_6$ -free graphs?
Can the general lower bound for arbitrary $H$ be improved from $2^{c_H \sqrt{\log n \log\log n}}$ to $2^{c_H (\log n)^\alpha}$ for some $\alpha > 1/2$ ?

References

Paul Erdős, András Hajnal (1989). Ramsey-type theorems · DOI:10.1016/0166-218X(89)90045-0
Maria Chudnovsky (2014). The Erdős–Hajnal conjecture—a survey · DOI:10.1002/jgt.21730
Matija Bucić, Tung Nguyen, Alex Scott, Paul Seymour (2024). Induced subgraph density. I. A loglog step towards Erdős–Hajnal · DOI:10.1093/imrn/rnae066 · arXiv:2301.10147
Tung Nguyen, Alex Scott, Paul Seymour (2023). Induced subgraph density. VII. The five-vertex path · arXiv:2312.15333 [preprint, not peer-reviewed]