Erdős–Hajnal conjecture

Remarks

Without the hypothesis on $H$, only a logarithmic bound holds. Every graph on $n$ vertices has a clique or an independent set of size at least $\tfrac12 \log_2 n$, by Ramsey's theorem. Random graphs show that this order $\log n$ cannot be improved in general. Erdős and Hajnal proved that excluding $H$ gives a bound of the form $e^{c\sqrt{\log n}}$ with $c > 0$ depending on $H$. The conjecture is known for all graphs $H$ with at most four vertices. For $H$ the path on four vertices it is easy: such graphs are perfect, so the product of the clique number and the independence number is at least $n$. The conjecture is open in general; the path on five vertices was settled only in 2023.