Erdős-Hajnal for graphs with no five-vertex path

Tung Nguyen, Princeton
Fine Hall 224

We discuss a proof of the Erdős-Hajnal conjecture for the five-vertex path; that is, every n-vertex graph with no induced five-vertex path contains a clique or stable set of size at least n^c. This completes the verification of the Erdős-Hajnal property of all five-vertex graphs.

Joint work with Alex Scott and Paul Seymour.