Bounded twin-width graphs are polynomially $\ddot{I}‡$-bounded

Abstract

We show that every graph with twin-width $t$ has chromatic number $O(\ddot{I}{‰}^{k_t})$ for some integer $k_t$, where $\ddot{I}‰$ denotes the clique number. This extends a quasi-polynomial bound from Pilipczuk and Sokołowski and generalizes a result for bounded clique-width graphs by Bonamy and Pilipczuk. The proof uses the main ideas of the quasi-polynomial approach, with a different treatment of the decomposition tree. In particular, we identify two types of extensions of a class of graphs: the delayed-extension (which preserves polynomial $\ddot{I}‡$-boundedness) and the right-extension (which preserves polynomial $\ddot{I}‡$-boundedness under bounded twin-width condition). Our main result is that every bounded twin-width graph is a delayed extension of simpler classes of graphs, each expressed as a bounded union of right extensions of lower twin-width graphs.