On an induced version of Menger's theorem

Kevin Hendrey, Sergey Norin, Raphael Steiner, Jérémie Turcotte

Published 2023-09-14Version 1

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.