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})$,其中$k_t$是一个整数,$\omega$表示团数。这扩展了Pilipczuk和Soko{\l}owski的准多项式上界,并将Bonamy和Pilipczuk对有界团宽图的结果推广。证明使用了准多项式方法的主要思想,并使用不同的分解树进行处理。特别的,我们鉴定了一类图的两种扩展方式:延迟扩展(保持多项式$\chi$-有界性质)和右扩展(在有界双宽条件下保证多项式$\chi$-有界性质)。我们的主要结果是每个被界限双宽图都可以被简单图的延迟扩展所替代,每个简单图都表示为较低双宽图的有界右扩展的有界并。