Sophie Spirkl, Princeton University

Abstract

For which graphs H is it true that there is an epsilon > 0 such that for all n > 1, and for every n-vertex graph G that does not contain H as an induced subgraph, either G has a vertex of degree at least epsilon n, or G contains two disjoint vertex sets A, B with |A|, |B| >= epsilon n, and there is no edge between A and B in G? Liebenau and Pilipczuk conjectured that this is true if H is a forest. I will talk about a proof of this conjecture, connections to the Erdos-Hajnal conjecture, and related questions. Joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.