Bounded twin-width graphs are polynomially $\chi$-bounded

Romain Bourneuf, Stéphan Thomassé

We show that every graph with twin-width $t$ has chromatic number $O({\omega }^{k_t})$ for some integer $k_t$, where $\omega$ denotes the clique number. This extends a quasi-polynomial bound fr…