Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.09839 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916935197786112 |
|---|---|
| author | Nguyen, Tung Scott, Alex Seymour, Paul |
| author_facet | Nguyen, Tung Scott, Alex Seymour, Paul |
| contents | In this paper, we develop a coarse analogue of treewidth. We prove that a graph $G$ admits a tree-decomposition in which each bag is contained in the union of a bounded number of balls of bounded radius, if and only if $G$ admits a quasi-isometry to a graph with bounded tree-width. (The ``if'' half is easy, but the ``only if'' half is challenging.) This generalizes a recent result of Berger and Seymour, concerning tree-decompositions when each bag has bounded radius. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_09839 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic structure. I. Coarse tree-width Nguyen, Tung Scott, Alex Seymour, Paul Combinatorics In this paper, we develop a coarse analogue of treewidth. We prove that a graph $G$ admits a tree-decomposition in which each bag is contained in the union of a bounded number of balls of bounded radius, if and only if $G$ admits a quasi-isometry to a graph with bounded tree-width. (The ``if'' half is easy, but the ``only if'' half is challenging.) This generalizes a recent result of Berger and Seymour, concerning tree-decompositions when each bag has bounded radius. |
| title | Asymptotic structure. I. Coarse tree-width |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.09839 |