The induced Menger conjecture for -free graphs
The induced Menger conjecture for -free graphs
Let be positive integers. Let be a -free graph, and let be disjoint. A set is a separator between and if deleting separates from ; write for the independence number of the subgraph induced by . An - path has one endpoint in and one in .
Induced Menger conjecture. There exists a function such that there exists either pairwise non-adjacent - paths, or a separator between and with .
This is proposed as an approximate induced analogue of Menger's theorem, motivated by the role of disjoint paths in proofs of grid theorems. The parser marks the conjecture as disproved; the paper cites counterexamples to proposed induced Menger variants.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Mujin Choi and Sebastian Wiederrecht, “Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars”, arXiv:2509.04026 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.