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. 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}})}$.

...
Wikipedia