***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Alex Scott (Oxford)
Thursday 17th February, 3:00, via Zoom. The Zoom link is
https://princeton.zoom.us/j/96636007111
and the password will be mailed to the seminar list.
Title: Polynomial bounds on chromatic number
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.
----------------------------------
Next week: Yuval Roichman
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)