A Menger-Type Theorem for Two Induced Paths
Sandra Albrechtsen, Tony Huynh, Raphael W. Jacobs, Paul Knappe, Paul Wollan · SIAM Journal on Discrete Mathematics · 2024
Abstract. We give an approximate Menger-type theorem for the case when a graph [Formula: see text] contains two [Formula: see text] paths [Formula: see text] and [Formula: see text] such that [Formula: see text] is an induced subgraph of [Formula: see text]. More generally, we prove that there exists a function [Formula: see text], such that for every graph [Formula: see text] and [Formula: see text], either there exist two [Formula: see text] paths [Formula: see text] and [Formula: see text] such that the distance between [Formula: see text] and [Formula: see text] is at least [Formula: see text], or there exists [Formula: see text] such that the ball of radius [Formula: see text] centered at [Formula: see text] intersects every [Formula: see text] path.