The Induced Menger Conjecture

About 1 year old · traced to

Let GG be a graph and let X,Y⊆V(G)X,Y\subseteq V(G). An (X,Y)(X,Y)-path is a path with one endpoint in XX and the other in YY, and two paths are anti-complete if they are vertex-disjoint and no edge of GG has one endpoint in each path. Write NG[Z]N_G[Z] for the closed neighbourhood of ZZ. The Induced Menger Conjecture. For every k∈Nk\in\mathbb{N}, every graph GG and X,Y⊆V(G)X,Y\subseteq V(G) satisfies one of the following: GG contains kk pairwise anti-complete (X,Y)(X,Y)-paths; or there exists a set Z⊆V(G)Z\subseteq V(G) with ∣Z∣⩽k−1|Z|\leqslant k-1 such that G−NG[Z]G-N_G[Z] has no (X,Y)(X,Y)-path. This is the induced analogue of Menger's theorem and corresponds to the d=2d=2 case of the coarse Menger conjecture; the paper's induced A\mathcal{A}-path theorem provides evidence but does not resolve it.

References

Primary source

Robert Hickingbotham and Gwenaël Joret, “An Induced A-Path Theorem”, arXiv:2512.17232 (2025).

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.