Papex

Open problem · Mathematics · since 1977 · Open

Erdős–Hajnal conjecture

For each graph H, is there a constant c > 0 such that every n-vertex graph with no induced copy of H has a clique or an independent set of at least n^c vertices?

Summary

Paul Erdős and András Hajnal posed it as an open problem in a 1977 paper and proved it when the excluded graph is a cograph. In random graphs both sizes are only logarithmic, so the conjecture says that excluding any one induced subgraph changes this; the case of an excluded five-vertex cycle has been proved by Chudnovsky, Scott, Seymour and Spirkl.

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 18 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics