Pith. sign in

REVIEW 1 cited by

A structural duality for path-decompositions into parts of small radius

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2307.08497 v3 pith:M5ZNULZV submitted 2023-07-17 math.CO

classification math.CO
keywords pathsresultssmallcyclesgraphgraphspartspath-decompositions
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Graph parameters that are coarsely equivalent to tree-length

    math.CO 2025-02 accept novelty 6.0 of 10

    Tree-length is within constant factors of bramble interception radius, Helly-family interception radius, same-vertex-set additive tree distortion, and two new cycle bridging parameters.

Pith tools