Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded

Author name not available (Why is that?)

Abstract: We prove that for every

t i n m a t h b b N

there is a constant

g a m m a_{t}

such that every graph with twin-width at most

t

and clique number

o m e g a

has chromatic number bounded by

2^{g a m m a_{t} l o g^{4 t + 3} o m e g a}

. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially

c h i

-bounded. This provides a significant step towards resolving the question of Bonnet et al. [ICALP 2021] about whether they are polynomially

c h i

-bounded.

No records found.

No records found.

This page was built for publication: Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded