A structural duality for path-decompositions into parts of small radius
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914620953853952 |
|---|---|
| author | Albrechtsen, Sandra Diestel, Reinhard Elm, Ann-Kathrin Fluck, Eva Jacobs, Raphael W. Knappe, Paul Wollan, Paul |
| author_facet | Albrechtsen, Sandra Diestel, Reinhard Elm, Ann-Kathrin Fluck, Eva Jacobs, Raphael W. Knappe, Paul Wollan, Paul |
| contents | It is an easy observation that if a graph~$G$ admits a path-decomposition whose parts have small radius, then $G$ contains no large subdivision of $K_{1,3}$ or $K^3$ as a (quasi-)geodesic subgraph. We show that these are in fact the only obstructions to such path-decompositions of small radial width, and we prove analogous results for decompositions modelled on cycles and subdivided stars instead of paths.
With our results we confirm in a strong form a conjecture of Georgakopoulos and Papasoglu on fat-minor-characterisations of graphs quasi-isometric to paths, cycles and paths, and subdivided stars, respectively. For this, we present a novel view on quasi-isometries between graphs by graph-decompositions of bounded radial width and spread. This new perspective enables us to prove further results in coarse graph theory, and may thus be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_08497 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A structural duality for path-decompositions into parts of small radius Albrechtsen, Sandra Diestel, Reinhard Elm, Ann-Kathrin Fluck, Eva Jacobs, Raphael W. Knappe, Paul Wollan, Paul Combinatorics 05C10 (Primary) 05C75, 05C12, 05C62, 05C83 (Secondary) It is an easy observation that if a graph~$G$ admits a path-decomposition whose parts have small radius, then $G$ contains no large subdivision of $K_{1,3}$ or $K^3$ as a (quasi-)geodesic subgraph. We show that these are in fact the only obstructions to such path-decompositions of small radial width, and we prove analogous results for decompositions modelled on cycles and subdivided stars instead of paths. With our results we confirm in a strong form a conjecture of Georgakopoulos and Papasoglu on fat-minor-characterisations of graphs quasi-isometric to paths, cycles and paths, and subdivided stars, respectively. For this, we present a novel view on quasi-isometries between graphs by graph-decompositions of bounded radial width and spread. This new perspective enables us to prove further results in coarse graph theory, and may thus be of independent interest. |
| title | A structural duality for path-decompositions into parts of small radius |
| topic | Combinatorics 05C10 (Primary) 05C75, 05C12, 05C62, 05C83 (Secondary) |
| url | https://arxiv.org/abs/2307.08497 |