Graphs of bounded twin-width are quasi-polynomially $\chi$-bounded

Abstract

We prove that for every $t\in \mathbb{N}$ there is a constant ${\gamma }_t$ such that every graph with twin-width at most $t$ and clique number $\omega$ has chromatic number bounded by $2^{{\gamma }_t{\log }^{4t+3}\omega }$. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially $\chi$-bounded. This provides a significant step towards resolving the question of Bonnet et al. [ICALP 2021] about whether they are polynomially $\chi$-bounded.

21 pages, 2 figures