Erdős–Hajnal conjecture

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal, who first posed it as an open problem in a paper from 1977.

More precisely, for an arbitrary undirected graph ${\displaystyle H}$, let ${\displaystyle {\mathcal {F}}_{H}}$ be the family of graphs that do not have ${\displaystyle H}$ as an induced subgraph. Then, according to the conjecture, there exists a constant ${\displaystyle \delta _{H}>0}$ such that the ${\displaystyle n}$-vertex graphs in ${\displaystyle {\mathcal {F}}_{H}}$ have either a clique or an independent set of size ${\displaystyle \Omega (n^{\delta _{H}})}$. In other words, for any hereditary family ${\displaystyle {\mathcal {F}}}$ of graphs that is not the family of all graphs, there exists a constant ${\displaystyle \delta _{\mathcal {F}}>0}$ such that the ${\displaystyle n}$-vertex graphs in ${\displaystyle {\mathcal {F}}}$ have either a clique or an independent set of size ${\displaystyle \Omega (n^{\delta _{\mathcal {F}}})}$.

A convenient and symmetric reformulation of the Erdős–Hajnal conjecture is that for every graph ${\displaystyle H}$, the ${\displaystyle H}$-free graphs necessarily contain a perfect induced subgraph of polynomial size. This is because every perfect graph necessarily has either a clique or independent set of size proportional to the square root of their number of vertices, and conversely every clique or independent set is itself perfect.

Background on the conjecture can be found in two surveys, one of András Gyárfás and the other of Maria Chudnovsky.