On an induced version of Menger's theorem

2023/09/14 by Hendrey, Kevin, Norin, Sergey, Steiner, Raphael +1 · 7 citations
#05C38 (Primary) 05C15 #05C40 #05C83 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2309.07905

Abstract

We prove Menger-type results in which the obtained paths are pairwise non-adjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topological minor. We further show better bounds in the subcubic case, and in particular obtain a tight result for two paths using a computer-assisted proof.

Cited by

• An Induced A-Path Theorem
• Dominated balanced separators in wheel-induced-minor-free graphs
• Asymptotic structure. V. The coarse Menger conjecture in bounded path-width
• Asymptotic structure. VI. Distant paths across a disc
• Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
• Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture
• Induced Minors, Asymptotic Dimension, and Baker's Technique

Related

• A generalisation of Menger's theorem in bidirected graphs
• A counterexample to the coarse Menger conjecture
• On Induced Versions of Menger's Theorem on Sparse Graphs
• Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture
• Asymptotic structure. VI. Distant paths across a disc