Problem 61

For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices that does not contain $H$ as an induced subgraph contains either a complete graph or independent set on $\geq n^c$ vertices?

Source: erdosproblems.com/61

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open: the site labels the problem OPEN (page last edited 10 April 2026), and the frontmatter standing is derived from the seven claim pages under claims/, all partial. Six are accepted on refereed publications: every $H$ on at most four vertices, by Erdős and Hajnal (claim page (Erdős and Hajnal, 1989)); the closure of the property under vertex substitution, by Alon, Pach and Solymosi (claim page (Alon, Pach and Solymosi, 2001)); the bull, by Chudnovsky and Safra (claim page (Chudnovsky and Safra, 2008)); $C_5$ , by Chudnovsky, Scott, Seymour and Spirkl (claim page (Chudnovsky, Scott, Seymour and Spirkl, 2021)); $P_5$ , and with the four pages before it every $H$ on at most five vertices, by Nguyen, Scott and Seymour (claim page (Nguyen, Scott and Seymour, 2023)); and an infinite family of $H$ with infinitely many prime members, by the same authors (claim page (Nguyen, Scott and Seymour, 2023)). One is claimed: Huang, Ju and Zhou's arXiv preprint of 4 June 2026 for two six-vertex graphs, the E-graph and the Bird graph (claim page (Huang, Ju and Zhou, 2026)). None settles the question for every $H$ , so the standing is open.

APS01: Alon, Noga and Pach, János and Solymosi, József, Ramsey-type theorems with forbidden subgraphs. Combinatorica (2001), 155-170.
BNSS23: Bucić, M. and Nguyen, T. and Scott, A. and Seymour, P., A loglog step towards Erdos-Hajnal. arXiv:2301.10147 (2023).
CSSS23: Chudnovsky, Maria and Scott, Alex and Seymour, Paul and Spirkl, Sophie, Erdős-Hajnal for graphs with no 5-hole. Proc. Lond. Math. Soc. (3) 126 (2023), no. 3, 997-1014, doi:10.1112/plms.12504.
ChSa08: Chudnovsky, Maria and Safra, Shmuel, The Erdős-Hajnal conjecture for bull-free graphs. J. Combin. Theory Ser. B 98 (2008), no. 6, 1301-1310, doi:10.1016/j.jctb.2008.02.005.
ErHa89: Erdős, P. and Hajnal, A., Ramsey-type theorems. Discrete Appl. Math. (1989), 37-52.
NSS24: Nguyen, Tung and Scott, Alex and Seymour, Paul, On a problem of El-Zahar and Erdős. J. Combin. Theory Ser. B 165 (2024), 211-222. The site's commentary credits the bound $2^{(\log n)^{1-o(1)}}$ for every path $H$ under this key, and the site's reference record resolves the key to this paper, which does not contain that bound: it concerns the El-Zahar–Erdős problem (Problem 1111) and does not mention the Erdős–Hajnal conjecture. The result the commentary describes is Tung Nguyen, Alex Scott and Paul Seymour, Induced subgraph density. V. All paths approach Erdős–Hajnal, arXiv:2307.15032 (2023).
NSS26: Nguyen, Tung and Scott, Alex and Seymour, Paul, Induced subgraph density. VII. The five-vertex path. Proc. Lond. Math. Soc. (3) 132 (2026), no. 3, Paper No. e70133, doi:10.1112/plms.70133.

Problem 61

Status

Proof claims

Discussion