Degeneracy of $P_t$-free and $C_{\ge t}$-free graphs with no large complete bipartite subgraphs

Abstract

A hereditary class of graphs $\mathcal{G}$ is \emph{$\chi$-bounded} if there exists a function $f$ such that every graph $G\in \mathcal{G}$ satisfies $\chi (G)\le 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 in 1985 that if $G$ is $P_t$-free, i.e., does not contain a $t$-vertex path as an induced subgraph, then $\chi (G)\le (t-1{)}^{\omega (G)-1}$. In 2017, Chudnovsky, Scott, and Seymour proved that $C_{\ge t}$-free graphs, i.e., graphs that exclude induced cycles with at least $t$ vertices, are $\chi$-bounded as well, and the obtained bound is again superpolynomial in the clique number. Note that $P_{t-1}$-free graphs are in particular $C_{\ge t}$-free. It remains a major open problem in the area whether for $C_{\ge t}$-free, or at least $P_t$-free graphs $G$, the value of $\chi (G)$ can be bounded from above by a polynomial function of $\omega (G)$. We consider a relaxation of this problem, where we compare the chromatic number with the size of a 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 and every $C_{\ge t}$-free graph which does not contain $K_{\ell ,\ell }$ as a subgraph, it holds that $\chi (G)\le {\ell }^c$.