Erdős–Hajnal conjecture

Open

erdos-hajnal

Statement

For every fixed graph $H$ , prove there is $c (H) > 0$ such that every $n$ -vertex graph with no induced copy of $H$ has a clique or independent set of size $\geq n^{c (H)}$ .

Current frontier

erdosproblems.com/61, OPEN. Erdős–Hajnal (1989) proved the weaker $e^{c l o g n}$ bound. The polynomial conjecture holds for all $H$ on $\leq 5$ vertices ( $C_{5}$ by Chudnovsky–Scott–Seymour–Spirkl 2023, $P_{5}$ by Nguyen–Scott–Seymour 2026), but is open in general.

When this counts as solved

OPEN-COMPLETION

PROOF_COMPLETE for all $H$ , COUNTEREXAMPLE for an $H$ forcing only $n^{o (1)}$ . BREAKTHROUGH for establishing the polynomial bound for a graph $H$ not already covered.

Classification

Open-completion

Mine this problem →