




















We show that every graph with twin-width $t$ has chromatic number $O(ω^{k_t})$ for some integer $k_t$, where $ω$ 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 $χ$-boundedness) and the right-extension (which preserves polynomial $χ$-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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。