A Menger-type conjecture for many induced paths

Let GG be a graph, let X,YV(G)X,Y\subseteq V(G), let d,k1d,k\geq 1 be integers, and let distG(Pi,Pj)\operatorname{dist}_G(P_i,P_j) denote the distance between paths in GG. For a set ZV(G)Z\subseteq V(G), let BG(Z,cd)B_G(Z,cd) denote its radius-cdcd neighborhood.

Many-path Menger-type conjecture. There exists a constant cc such that, for all such GG, XX, YY, dd, and kk, either there exist kk disjoint XYX-Y paths P1,,PkP_1,\dots,P_k satisfying

distG(Pi,Pj)d\operatorname{dist}_G(P_i,P_j)\geq d

for all distinct i,ji,j, or there exists a set ZV(G)Z\subseteq V(G) of size at most k1k-1 such that BG(Z,cd)B_G(Z,cd) intersects every XYX-Y path.

This conjectures a many-path extension of the paper's two-path theorem, which gives such a constant-radius obstruction for two paths. The corresponding exact characterization is motivated by Menger's theorem but is not known for paths required to be pairwise far apart.

Sources & referencesView supporting material

Primary source

Sandra Albrechtsen, Tony Huynh, Raphael W. Jacobs, Paul Knappe and Paul Wollan, “A Menger-type theorem for two induced paths”, arXiv:2305.04721 (2024).

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.