Induced Menger separation with bounded degree

Conjecture 1.4 · arXiv:2309.07905

arXiv Conjecture high confidence— first stated 2023-09-14

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

Status open medium confidence

Conjecture 1.4 from arXiv:2309.07905 asks, for every d and bounded-degree graph, for either k pairwise distance-d X-Y paths or a linear separator of size Ck. The source paper itself proves the first non-trivial case d=2 (Theorem 1.5), and independent concurrent work by Gartland–Korhonen–Lokshtanov (arXiv:2309.08169) establishes a similar result for bounded-degree graphs. An active line of research by Nguyen–Scott–Seymour on 'coarse Menger' problems addresses related settings (planar graphs, bounded path-width) but the general conjecture for all d and bounded degree Δ has not been resolved in the verified literature.

Reviewer notes. The d=2 case was already proved in the source paper as Theorem 1.5, so no 'since_posted' entry is warranted for that. Related 'coarse Menger' work (arXiv:2509.07174; arXiv:2605.11112) targets planar and bounded-genus settings or stronger Conjectures 1.2 of the same paper, not specifically Conjecture 1.4 for all d and bounded degree; those papers could not be confirmed to address the conjecture directly within the 5-call budget. Confidence is medium because the research area is very active and further progress may exist but was not found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every $d, \Delta \in \mathbb{N}$ there exists a constant $C = C(d, \Delta) > 0$ such that the following holds. If $k \in \mathbb{N}$, $G$ is a graph with $\Delta(G) \leq \Delta$ and $X, Y \subseteq V(G)$, then there exists either (1) $k$ $X$-$Y$-paths pairwise at distance at least $d$ in $G$, or (2) a set of less than $Ck$ vertices in $G$ which separates $X$ and $Y$.

Context

This conjecture is derived as a consequence of the stronger (c independent of k) form of Conjecture 1.2 for graphs of bounded maximum degree $\Delta$: the ball $B_G(Z, cd)$ can be bounded in size by $\Delta^{cd+1}k$, yielding a linear separator of size $Ck$. The paper proves this conjecture in the first non-trivial case $d = 2$ as its first main result (Theorem 1.5).

Notes. PDF source. The $d = 2$ case is proved within the paper (Theorem 1.5); the conjecture for $d \geq 3$ remains open.

Source paper

On an induced version of Menger's theorem
Kevin Hendrey, Sergey Norin, Raphael Steiner, Jérémie Turcotte · 2023-09-14
https://arxiv.org/abs/2309.07905 PDF source