Back to Search
Start Over
Graphs of bounded twin-width are quasi-polynomially $\chi$-bounded
- 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
- Subjects :
- Mathematics - Combinatorics
Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2202.07608
- Document Type :
- Working Paper