Leírás
Abstract:
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\'{a}rf\'{a}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}$.
Joint work with Marthe Bonamy, Nocolas Bousquet, Michał Pilipczuk, Stephan Thomasse, and Bartosz Walczak.
https://zoom.us/j/98689592820?pwd=SndCRGJoTzhwYkNCT0hNQnJIaXk3dz09