A structural duality for path-decompositions into parts of small radius
It is an easy observation that if a graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> admits a path-decomposition whose parts have small radius, then <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> contains no large subdivision of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msub> </mml:math> or <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>K</mml:mi> <mml:mn>3</mml:mn> </mml:msup> </mml:math> 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.
Authors
- Sandra Albrechtsen
- Raphael W. Jacobs (ORCID: https://orcid.org/0000-0003-0339-9435)
- Reinhard Diestel (ORCID: https://orcid.org/0000-0002-2825-442X)
- Paul Wollan
- Eva Fluck (ORCID: https://orcid.org/0000-0002-9643-6081)
- Ann-Kathrin Elm
- Paul Knappe (ORCID: https://orcid.org/0000-0002-4569-1410)
Institutions
- Universität Hamburg (DE)
- Heidelberg University (DE)
- Hochschule für bildende Künste (DE)
- Sapienza University of Rome (IT)
- RWTH Aachen University (DE)
Publication Details
- Journal
- Innovations in Graph Theory
- Published
- 2026-05-21
- DOI
- https://doi.org/10.5802/igt.22
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint
- Field-Weighted Citation Impact
- 0.00