The bounded-degree induced Menger conjecture

Let GG be a graph, let Δ(G)\Delta(G) denote its maximum degree, and let X,YV(G)X,Y\subseteq V(G). A set of vertices separates XX and YY if it intersects every XX-YY-path; paths are pairwise at distance at least dd when their graph distance in GG is at least dd. The bounded-degree induced Menger conjecture. For every d,ΔNd,\Delta\in\mathbb{N}, there exists a constant C=C(d,Δ)>0C=C(d,\Delta)>0 such that, for every kNk\in\mathbb{N} and every graph GG with Δ(G)Δ\Delta(G)\leq\Delta, together with X,YV(G)X,Y\subseteq V(G), there exists either

k X-Y-paths pairwise at distance at least d in G,k\text{ }X\text{-}Y\text{-paths pairwise at distance at least }d\text{ in }G,

or a set of fewer than CkCk vertices in GG that separates XX and YY. This is presented as a necessary consequence of the stronger coarse Menger conjecture of Albrechtsen et al. The source does not report a resolution of this bounded-degree formulation.

Sources & referencesView supporting material

Primary source

Kevin Hendrey, Sergey Norin, Raphael Steiner and Jérémie Turcotte, “On an induced version of Menger's theorem”, arXiv:2309.07905 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.