On Induced Versions of Menger's Theorem on Sparse Graphs
share
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 Δ be the maximum degree of G. We show that there exists a function f(Δ) = (Δ+1)^Δ^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 · f(Δ) 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].
READ FULL TEXT