On an Induced Version of Menger's Theorem
OPEN ACCESS
Author / Producer
Date
2024-11-01
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Abstract
We prove Menger-type results in which the obtained paths are pairwise nonadjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topological minor. More precisely, we show the existence of a constant C, depending only on the maximum degree or on the forbidden topological minor, such that for any pair of sets of vertices X, Y and any positive integer k, there exist either k pairwise non-adjacent X-Y-paths, or a set of fewer than Ck vertices which separates X and Y. We further show better bounds in the sub cubic case, and in particular obtain a tight result for two paths using a computer-assisted proof.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
31 (4)
Pages / Article No.
Publisher
Electronic Journal of Combinatorics