2023/09/15 by Peter Gartland, Gartland, Peter, Tuukka Korhonen +3 · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2309.08169
openalex publication_date 2023/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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].