A Menger-type conjecture for many induced paths
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.