Bounded twin-width graphs are polynomially $χ$-bounded
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909458920112128 |
|---|---|
| author | Bourneuf, Romain Thomassé, Stéphan |
| author_facet | Bourneuf, Romain Thomassé, Stéphan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_11231 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Bounded twin-width graphs are polynomially $χ$-bounded Bourneuf, Romain Thomassé, Stéphan Discrete Mathematics Combinatorics 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. |
| title | Bounded twin-width graphs are polynomially $χ$-bounded |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2303.11231 |