A structural duality for path-decompositions into parts of small radius
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Various Properties of Various Ultrafilters, Various Graph Width Parameters, and Various Connectivity Systems (with Survey)
The work develops properties of ultrafilters, prefilters, and related notions on connectivity systems while surveying a range of graph width, length, and depth parameters.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.