Bounded twin-width graphs are polynomially \chi-bounded

Authors Romain Bourneuf, Stéphan Thomassé

Publication date 20 March 2023

Abstract: We show that every graph with twin-width

t

has chromatic number

O (o m e g a^{k_{t}})

for some integer

k_{t}

, where

o m e g a

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

c h i

-boundedness) and the right-extension (which preserves polynomial

c h 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.

This page was built for publication: Bounded twin-width graphs are polynomially $\chi$-bounded

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6430213)