Back to Search Start Over

Graphs of bounded twin-width are quasi-polynomially $\chi$-bounded

Authors :
Pilipczuk, Michał
Sokołowski, Marek
Publication Year :
2022

Abstract

We prove that for every $t\in \mathbb{N}$ there is a constant $\gamma_t$ such that every graph with twin-width at most $t$ and clique number $\omega$ has chromatic number bounded by $2^{\gamma_t \log^{4t+3} \omega}$. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially $\chi$-bounded. This provides a significant step towards resolving the question of Bonnet et al. [ICALP 2021] about whether they are polynomially $\chi$-bounded.<br />Comment: 21 pages, 2 figures

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2202.07608
Document Type :
Working Paper