REVIEW 8 cited by
Asymptotic structure. I. Coarse tree-width
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
Asymptotic structure. I. Coarse tree-width
read the original abstract
In this paper, we develop a coarse analogue of tree-width. 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. We also prove a similar result for line-width, which is an extension of path-width to infinite graphs.
Forward citations
Cited by 8 Pith papers
-
Asymptotic structure. III. Excluding a fat tree
Any graph lacking a c-fat tree minor can be quasi-isometrically approximated by a graph with line-width bounded in terms of the tree and c.
-
Optimal tree-decompositions with bags of bounded pathwidth
Every planar graph admits an optimal tree-decomposition in which every bag induces a subgraph of pathwidth at most 3, with an O(k) bound on unions of k bags, and analogues for fixed-surface graphs.
-
Vertex cuts and median decompositions
Median decompositions arise from any system of vertex cuts via Sageev's dual median graph, are uniquely minimal, satisfy median-width equals clique number on all graphs, and characterize proper geometric actions of gr...
-
A coarse Menger's Theorem for planar and bounded genus graphs
In planar and bounded-genus graphs, absence of k pairwise d-far S-T paths implies a vertex set of size f(d,k) whose d-neighborhood intersects every S-T path.
-
Coarse Menger property of quasi-minor excluded graphs and length spaces
Locally finite graphs with an excluded finite minor have the weak coarse Menger property with f depending only on k and g linear in r independent of k.
-
Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
Every K_{1,d}-free graph that excludes the k-ladder as an induced minor has tree-independence number bounded by a function of k and d.
-
A coarse block-cut tree theorem
Every graph admits a tree decomposition with small-diameter adhesion sets where same-bag vertices cannot be separated by small, distant vertex sets.
-
A coarse block-cutvertex tree-decomposition
Every connected graph has a tree-decomposition with bounded-diameter adhesion sets and coarsely inseparable bags, yielding a metric analogue of the block-cutvertex tree.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.