Speaker: Marthe Bonamy

Title: Towards polynomial Chi-boundedness of graphs with no long path

Abstract:
There are graphs of arbitrarily high chromatic number which contain no triangle and in fact no short cycle. However, in some graph classes with enough structure, we can show that the chromatic number of the graphs is bounded by some function of their largest clique -- in other words, that class is chi-bounded. One of the first such results was by Gyarfas in 1987: for any t, the class of Pt-free graphs is chi-bounded. The corresponding function is unfortunately exponential, and it remains a major open problem whether we can replace it with a polynomial. Here, we consider a relaxation of this problem, where we compare the chromatic number with the size of the largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every t there exists a constant c such that every Pt-free graph which does not contain Kp,p as a subgraph is p^c-colourable. This is joint work with Nicolas Bousquet, Michal Pilipczuk, Pawel Rzazewski, Stéphan Thomassé and Bartosz Walczak.