REVIEW 5 cited by
On Induced Versions of Menger's Theorem on Sparse Graphs
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
On Induced Versions of Menger's Theorem on Sparse Graphs
read the original abstract
Let $A$ and $B$ be sets of vertices in a graph $G$. Menger's theorem states that for every positive integer $k$, either there exists a collection of $k$ vertex-disjoint paths between $A$ and $B$, or $A$ can be separated from $B$ by a set of at most $k-1$ vertices. Let $\Delta$ be the maximum degree of $G$. We show that there exists a function $f(\Delta) = (\Delta+1)^{\Delta^2+1}$, so that for every positive integer $k$, either there exists a collection of $k$ vertex-disjoint and pairwise anticomplete paths between $A$ and $B$, or $A$ can be separated from $B$ by a set of at most $k \cdot f(\Delta)$ vertices. We also show that the result can be generalized from bounded-degree graphs to graphs excluding a topological minor. On the negative side, we show that no such relation holds on graphs that have degeneracy 2 and arbitrarily large girth, even when $k = 2$. Similar results were obtained independently and concurrently by Hendrey, Norin, Steiner, and Turcotte [arXiv:2309.07905].
Forward citations
Cited by 5 Pith papers
-
Fatness and Flatness
Excluding a fixed graph as a fat minor forces a metric analog of uniform quasi-wideness; this bounds scatter dimension and yields EPAS-style approximation for norm k-clustering.
-
A coarse Menger theorem for hyperbolic graphs, finitely presented groups, and more
Graphs with cycle spaces generated by bounded-length cycles have the coarse Menger property, with corollaries for hyperbolic graphs, finitely presented groups, and planar graphs with bounded faces.
-
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.
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.