A Menger-type conjecture for many induced paths
Let be a graph, let , let be integers, and let denote the distance between paths in . For a set , let denote its radius- neighborhood.
Many-path Menger-type conjecture. There exists a constant such that, for all such , , , , and , either there exist disjoint paths satisfying
for all distinct , or there exists a set of size at most such that intersects every 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
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.