-
Paul Seymour, The Erdős-Hajnal conjecture is true for excluding a five-cycle
Paul Seymour, The Erdős-Hajnal conjecture is true for excluding a five-cycle
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 …