Towards polynomial Chi-boundedness of graphs with no long path

A hereditary class of graphs $\mathcal{G}$ is {\em{$\chi$-bounded}} if there exists a function $f$ such that for every $G \in \mathcal{G}$ it holds that $\chi(G) \leq f(\omega(G))$, where $\chi(G)$ and $\omega(G)$ are the chromatic number and the clique number of $G$, respectively. As one of the first results about $\chi$-bounded classes, Gyárfás proved already in 1987 that if $G$ is $P_t$-free, i.e., does not contain a $t$-vertex path as an induced subgraph, then $\chi(G) \leq (t-1)^{\omega(G)-1}$. It remains a major open problem in the area whether for $P_t$-free graphs $G$ the value of $\chi(G)$ can be upper-bounded by a polynomial function of $\omega(G)$. 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 for every $P_t$-free graph which does not contain $K_{\ell,\ell}$ as a subgraph, it holds that $\chi(G) \leq \ell^{c}$. This is joint work with Nicolas Bousquet, Michał Pilipczuk, Paweł Rzáżewski, Stéphan Thomassé and Bartosz Walczak.