A Menger-type conjecture for many induced paths

About 3 years old · traced to

Let GG be a graph, let X,Y⊆V(G)X,Y\subseteq V(G), let d,k≥1d,k\geq 1 be integers, and let dist⁡G(Pi,Pj)\operatorname{dist}_G(P_i,P_j) denote the distance between paths in GG. For a set Z⊆V(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 X−YX-Y paths P1,…,PkP_1,\dots,P_k satisfying

dist⁡G(Pi,Pj)≥d\operatorname{dist}_G(P_i,P_j)\geq d

for all distinct i,ji,j, or there exists a set Z⊆V(G)Z\subseteq V(G) of size at most k−1k-1 such that BG(Z,cd)B_G(Z,cd) intersects every X−YX-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.

References

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.