Math Conjectures

Erdős–Hajnal Conjecture

OPENLandmarkConjectureProposed 1977–1989 · Standard version

Canonical statement

For every finite graph HH, there exists ε(H)>0\varepsilon(H)>0 such that every nn-vertex simple graph GG with no induced subgraph isomorphic to HH has either a clique or an independent set of size at least nε(H)n^{\varepsilon(H)}.
View source LaTeX
For every finite graph \(H\), there exists
\(\varepsilon(H)>0\) such that every \(n\)-vertex simple graph \(G\) with
no induced subgraph isomorphic to \(H\) has either a clique or an
independent set of size at least \(n^{\varepsilon(H)}\).
GRAPH-011:[ErdosHajnal1989][Chudnovsky2014EH][NguyenScottSeymour2026P5]
Graph theoryCombinatorics

Notes

The Erdős–Hajnal conjecture asserts that for every finite graph HH there is an ε(H)>0\varepsilon(H)>0 such that every nn-vertex graph with no induced copy of HH contains a clique or an independent set of size at least nε(H)n^{\varepsilon(H)}. This is dramatically stronger than the logarithmic guarantee that Ramsey's theorem provides for general graphs. The conjecture emerged in work of Erdős and Hajnal in the late 1970s and appeared in their 1989 paper on Ramsey-type theorems [ErdosHajnal1989], which accounts for the 1977–1989 dating.

The conjecture is known for many forbidden graphs HH, and the class of graphs for which it holds is preserved under useful composition operations; Chudnovsky's survey describes this landscape [Chudnovsky2014EH]. In June 2026, Nguyen, Scott, and Seymour proved the long-open case of the five-vertex path H=P5H=P_5, which completed the conjecture for every forbidden graph on at most five vertices [NguyenScottSeymour2026P5].

For arbitrary HH, however, the conjecture remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.