Induced trees and Erdos-Hajnal

Induced trees and Erdos-Hajnal

-
Alex Scott. Oxford University
Fine Hall 224

A hereditary class of graphs has the Erdos-Hajnal property if there is some c>0 such that every graph G in the class contains a complete graph or independent set of size at least |G|^c. The Erdos-Hajnal Conjecture asserts that for every graph H the class of graphs with no induced copy of H has the Erdos-Hajnal property. Resolving a conjecture of Liebenau and Pilipczuk, we show that, for every forest T, the class of graphs with no induced copy of T or its complement has the Erdos-Hajnal property. This is joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.