Pith. sign in

Asymptotic structure. III. Excluding a fat tree

2 Pith papers cite this work. Polarity classification is still indexing.

2 Pith papers citing it
abstract

Robertson and Seymour proved that for every finite tree $H$, there exists $k$ such that every finite graph $G$ with no $H$ minor has path-width at most $k$; and conversely, for every integer $k$, there is a finite tree $H$ such that every finite graph $G$ with an $H$ minor has path-width more than $k$. If we (twice) replace ``path-width'' by ``line-width'', the same is true for infinite graphs $G$. We prove a ``coarse graph theory'' analogue, as follows. For every finite tree $H$ and every $c$, there exist $k,L,C$ such that every graph that does not contain $H$ as a $c$-fat minor admits an $(L,C)$-quasi-isonetry to a graph with line-width at most $k$; and conversely, for all $k,L,C$ there exist $c$ and a finite tree $H$ such that every graph that contains $H$ as a $c$-fat minor admits no $(L,C)$-quasi-isometry to a graph with line-width at most $k$.

citation-role summary

background 1

citation-polarity summary

fields

math.CO 2

years

2026 2

roles

background 1

polarities

background 1

representative citing papers

A coarse block-cut tree theorem

math.CO · 2026-07-08 · accept · novelty 6.0

Every graph admits a tree decomposition with small-diameter adhesion sets where same-bag vertices cannot be separated by small, distant vertex sets.

citing papers explorer

Showing 2 of 2 citing papers.

  • A coarse Menger's Theorem for planar and bounded genus graphs math.CO · 2026-05-11 · unverdicted · none · ref 38 · internal anchor

    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.

  • A coarse block-cut tree theorem math.CO · 2026-07-08 · accept · none · ref 18 · internal anchor

    Every graph admits a tree decomposition with small-diameter adhesion sets where same-bag vertices cannot be separated by small, distant vertex sets.