Bounded twin-width graphs are polynomially $χ$-bounded

While the chromatic number $\chi(G)$ of a graph $G$ is at least its clique number $\omega(G)$, it is a classical result that there exist triangle-free graphs with arbitrarily large chromatic number, so the chromatic number is in general not upper-bounded by a function of the clique number.

Let us say that a class of graphs is $\chi$-bounded if there is a function $f$ such that for any graph $G$ in the class, $\chi(G)\le f(\omega(G))$. The paragraph above shows that the class of all graphs is not $\chi$-bounded. However a number of more restricted classes are $\chi$-bounded: This is the case for instance for perfect graphs (where equality holds), and more generally for graphs with no odd induced cycles of length at least $\ell$, for any fixed $\ell$ (as proved by Chudnovsky, Scott, Seymour, and Spirkl).

The Gyárfás-Sumner conjecture asserts that for any tree $T$, the class of graphs which do not contain any induced copy of $T$ is $\chi$-bounded. If the Gyárfás-Sumner conjecture was true, with a polynomial function $f$ relating the clique and chromatic numbers, then this would directly imply another classical conjecture in the case of trees, the Erdős-Hajnal conjecture, which states that for any graph $H$, every graph which does not contain any induced copy of $H$ has a clique or stable set of polynomial size.

So let us say that a class of graphs is polynomially $\chi$-bounded if there is a polynomial $f$ such that for any graph $G$ in the class, $\chi(G)\le f(\omega(G))$. Much less is known about polynomially $\chi$-bounded classes. It was only proved quite recently (by Briański, Davies, and Walczak) that there exist hereditary classes that are $\chi$-bounded but not polynomially $\chi$-bounded.

The present paper proves that any class of bounded twin-width is polynomially $\chi$-bounded. This extends an earlier result of Bonamy and Pilipczuk on graphs of bounded rankwidth. The proof heavily builds on a recent result of Pilipczuk and Sokołowski showing a quasi-polynomial bound (instead of a polynomial bound).

Classes of bounded twin-width are one of the most general classes of graphs which are known to be polynomially $\chi$-bounded. Bounded twin-width graphs (or structures) include proper minor-closed classes, graphs of bounded rankwidth, posets of bounded width, pattern-avoiding permutations, and some constructions of expander graph families. Any first-order interpretation or transduction of a class of bounded twin-width again has bounded twin-width, so for instance the class of all squares of planar graphs has bounded twin-width.