The induced Menger conjecture for K1,dK_{1,d}-free graphs

Let k,dk,d be positive integers. Let GG be a K1,dK_{1,d}-free graph, and let A,B⊆V(G)A,B\subseteq V(G) be disjoint. A set SS is a separator between AA and BB if deleting SS separates AA from BB; write α(S)\alpha(S) for the independence number of the subgraph induced by SS. An AA-BB path has one endpoint in AA and one in BB.

Induced Menger conjecture. There exists a function f:N2→Nf:\mathbb{N}^2\rightarrow\mathbb{N} such that there exists either kk pairwise non-adjacent AA-BB paths, or a separator SS between AA and BB with α(S)<f(k,d)\alpha(S)<f(k,d).

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.

References

Primary source

Mujin Choi and Sebastian Wiederrecht, “Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars”, arXiv:2509.04026 (2025).

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.