PaulSeymour

In an n-vertex graph, there must be a clique or stable set of size at least $C\log n$, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph, the largest clique or stable set is bigger. Erdős and Hajnal conjectured in 1977 that …

The Gyárfás-Sumner conjecture says that for every forest $H$, there is a function $f$ such that the chromatic number $\chi (G)$ is at most $f(\omega (G))$ for every $H$-free graph $G$ ("$H$-free" means with no induced subgraph isomorphic to $H$, and $\omega (G)$ is the size of the largest clique of $G$). This well-known conjecture has been proved only for a …

In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G{|}^c$; and they proved that this is true with $|G{|}^c$ replaced by $2^{c\sqrt{\log |G|}}$. There has no improvement on this result (for general …