On an Induced Version of Menger's Theorem
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.
Authors
- Sergey Norin (ORCID: https://orcid.org/0000-0003-4833-7983)
- Raphael Steiner (ORCID: https://orcid.org/0000-0002-4234-6136)
- Jérémie Turcotte (ORCID: https://orcid.org/0000-0002-4555-8425)
- Kevin Hendrey
Institutions
- Center for Discrete Mathematics and Theoretical Computer Science (US)
- ETH Zurich (CH)
- Institute for Basic Science (KR)
- Laboratoire d'Informatique de Paris-Nord (FR)
- McGill University (CA)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2024-10-31
- DOI
- https://doi.org/10.37236/12575
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Eidgenössische Technische Hochschule Zürich
- Institute for Basic Science
- Natural Sciences and Engineering Research Council of Canada