1Discrete Mathematics Group, Institute for Basic Science (IBS) 2Department of Mathematics and Statistics, McGill University 3Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich
The electronic journal of combinatorics, Tome 31 (2024) no. 4
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. 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 exists either $k$ pairwise non-adjacent $X\text{-}Y$-paths, or a set of fewer than $Ck$ vertices which separates $X$ and $Y$. We further show better bounds in the subcubic case, and in particular obtain a tight result for two paths using a computer-assisted proof.
1
Discrete Mathematics Group, Institute for Basic Science (IBS)
2
Department of Mathematics and Statistics, McGill University
3
Institute of Theoretical Computer Science, Department of Computer Science, ETH Zürich
@article{10_37236_12575,
author = {Kevin Hendrey and Sergey Norin and Raphael Steiner and J\'er\'emie Turcotte},
title = {On an induced version of {Menger's} theorem},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {4},
doi = {10.37236/12575},
zbl = {1551.05216},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12575/}
}
TY - JOUR
AU - Kevin Hendrey
AU - Sergey Norin
AU - Raphael Steiner
AU - Jérémie Turcotte
TI - On an induced version of Menger's theorem
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/12575/
DO - 10.37236/12575
ID - 10_37236_12575
ER -
%0 Journal Article
%A Kevin Hendrey
%A Sergey Norin
%A Raphael Steiner
%A Jérémie Turcotte
%T On an induced version of Menger's theorem
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/12575/
%R 10.37236/12575
%F 10_37236_12575
Kevin Hendrey; Sergey Norin; Raphael Steiner; Jérémie Turcotte. On an induced version of Menger's theorem. The electronic journal of combinatorics, Tome 31 (2024) no. 4. doi: 10.37236/12575
