Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2501.10840 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911111818772480 |
|---|---|
| author | Hickingbotham, Robert |
| author_facet | Hickingbotham, Robert |
| contents | In this paper, we characterise graphs that are quasi-isometric to graphs with bounded treewidth. Specifically, we prove that a graph is quasi-isometric to a graph with bounded treewidth if and only if it has a tree-decomposition where each bag consists of a bounded number of balls of bounded diameter. This result extends a characterisation by Berger and Seymour (2024) of graphs that are quasi-isometric to trees. Additionally, we characterise graphs that are quasi-isometric to graphs with bounded pathwidth and graphs that are quasi-isometric to graphs with bounded linewidth. As an application of these results, we show that graphs with bounded rank-width, graphs with bounded tree independence number, and graphs with bounded sim-width are quasi-isometric to graphs with bounded treewidth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_10840 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graphs that are quasi-isometric to graphs with bounded treewidth Hickingbotham, Robert Combinatorics In this paper, we characterise graphs that are quasi-isometric to graphs with bounded treewidth. Specifically, we prove that a graph is quasi-isometric to a graph with bounded treewidth if and only if it has a tree-decomposition where each bag consists of a bounded number of balls of bounded diameter. This result extends a characterisation by Berger and Seymour (2024) of graphs that are quasi-isometric to trees. Additionally, we characterise graphs that are quasi-isometric to graphs with bounded pathwidth and graphs that are quasi-isometric to graphs with bounded linewidth. As an application of these results, we show that graphs with bounded rank-width, graphs with bounded tree independence number, and graphs with bounded sim-width are quasi-isometric to graphs with bounded treewidth. |
| title | Graphs that are quasi-isometric to graphs with bounded treewidth |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.10840 |