Asymptotic structure. V. The coarse Menger conjecture in bounded path-width

Abstract

Menger's theorem tells us that if $S,T$ are sets of vertices in a graph $G$, then (for $k\ge 0$) either there are $k+1$ vertex-disjoint paths between $S$ and $T$, or there is a set of $k$ vertices separating $S$ and $T$. But what if we want the paths to be far apart, say at distance at least $c$? One might hope that we can find either $k+1$ paths pairwise far apart, or $k$ sets of bounded radius that separate $S$ and $T$, where the bound on the radius is some $\ell$ that depends only on $k,c$ (the ``coarse Menger conjecture''). The last three authors showed in an earlier paper that this is false for all $k\ge 2$ and $c\ge 3$, by constructing a sequence of finite graphs giving counterexamples for larger and larger values of $\ell$ with $k=2$ and $c=3$. These counterexamples contained subdivisions of uniform binary trees with arbitrarily large depth as subgraphs, and so had unbounded path-width. Here we show that, if $H$ is a graph that can be drawn in the plane such that each region shares a vertex with the infinite region, then the coarse Menger conjecture is true for all graphs not containing $H$ as a minor. Consequently, the conjecture is true for all graphs with bounded path-width (by taking $H$ to be a sufficiently large tree), and it is true for series-parallel graphs (by taking $H=K_4$). The first is somewhat surprising, since the conjecture is false for bounded tree-width.

v2: 29 pages, main result strengthened and one coauthor added