Online Talk

The Gyarfas-Sumner conjecture asserts that, for every forest H and integer k, every graph with sufficiently large chromatic number contains either an induced copy of H or a copy of the complete graph K_k. An old result of Rodl shows that the statement is true if instead of K_k we ask for a complete bipartite graph K_{t,t} (as a subgraph, so not necessarily induced). The bounds in Rodl's theorem (and in most known cases of the Gyarfas-Sumner conjecture) are quite large. Here we address the question: when can they be taken to be polynomial? A polynomial version of Rodl's theorem is known for paths: Bonamy, Bousquet, Pilipczuk, Rzazewski, Thomasse and Walczak proved that for every path H there is a polynomial f such that if G has chromatic number at least f(t) then G contains either an induced copy of H or a complete bipartite subgraph K_{t,t}. We show that in fact Rodl's theorem holds with polynomial bounds for every forest H. We will also discuss cases where a polynomial version of the Gyarfas-Sumner conjecture is known, and the relationship with the Erdos-Hajnal conjecture. Includes joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.