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\sqrt{\log n}}

bound. The polynomial conjecture holds for all

H

\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