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) 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{a}rf{a}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) leq (t-1)^{omega(G)-1}$. In 2017, Chudnovsky, Scott, and Seymour proved that $C_{geq 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_{geq t}$-free. It remains a major open problem in the area whether for $C_{geq 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_{geq t}$-free graph which does not contain $K_{ell,ell}$ as a subgraph, it holds that $chi(G) leq ell^{c}$.
Download