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

From papers

Let k,dk,d be positive integers. Let GG be a K1,dK_{1,d}-free graph, and let A,BV(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:N2Nf:\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.

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

No solutions have been posted yet.