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 from Pilipczuk and Soko{\l}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 $\chi$-boundedness) and the right-extension (which preserves polynomial $\chi$-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.
翻译:我们证明了具有双宽度$t$的图的染色数为$O(\omega ^{k_t})$,其中$\omega$表示最大团数。这扩展了Pilipczuk和Soko{\l}owski的拟多项式上界,并推广了Bonamy和Pilipczuk对有界团宽度图的结果。证明使用了拟多项式方法的主要思想,但对分解树的处理略有不同。特别是,我们确定了一类图形的两种扩展:延迟扩展(保持多项式$\chi$-有界)和右扩展(在有界双宽度条件下保持多项式$\chi$-有界)。我们的主要结果是:每个有界双宽图形都是较简单类图的延迟扩展,每个较简单类图可以表示为较低双宽图的右扩展的有界并。