Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2505.09834 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913854412292096 |
|---|---|
| author | Distel, Marc |
| author_facet | Distel, Marc |
| contents | Cliquewidth is a dense analogue of treewidth. It can be deduced from recent results by Hickingbotham [arXiv:2501.10840] and Nguyen, Scott, and Seymour [arXiv:2501.09839] that graphs of bounded cliquewidth are quasi-isometric to graphs of bounded treewidth. We improve on this by showing that graphs of cliquewidth $k$ admit a partition with `local, but dense' parts whose quotient has treewidth $k-1$. Specifically, each part is contained within the closed neighbourhood of some vertex. We use this to construct a $3$-quasi-isometry between graphs of cliquewidth $k$ and graphs of treewidth $k-1$. This is an improvement in both the quasi-isometry parameter and the treewidth. We also show that the bound on the treewidth is tight up to an additive constant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_09834 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An improved quasi-isometry between graphs of bounded cliquewidth and graphs of bounded treewidth Distel, Marc Combinatorics Cliquewidth is a dense analogue of treewidth. It can be deduced from recent results by Hickingbotham [arXiv:2501.10840] and Nguyen, Scott, and Seymour [arXiv:2501.09839] that graphs of bounded cliquewidth are quasi-isometric to graphs of bounded treewidth. We improve on this by showing that graphs of cliquewidth $k$ admit a partition with `local, but dense' parts whose quotient has treewidth $k-1$. Specifically, each part is contained within the closed neighbourhood of some vertex. We use this to construct a $3$-quasi-isometry between graphs of cliquewidth $k$ and graphs of treewidth $k-1$. This is an improvement in both the quasi-isometry parameter and the treewidth. We also show that the bound on the treewidth is tight up to an additive constant. |
| title | An improved quasi-isometry between graphs of bounded cliquewidth and graphs of bounded treewidth |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.09834 |