Polynomial minimal separators or bounded hole length for induced-minor-free graphs

Let GG be a graph. A clique cutset is a clique whose deletion disconnects GG, a minimal separator is a minimal vertex set separating two vertices of GG, and a hole is an induced cycle of length at least four. An induced minor of GG is obtained by deleting vertices and contracting edges.

Polynomial-separator or bounded-hole conjecture. There exists a polynomial pp and an integer kk such that if GG has no clique cutset and does not contain K2,3K_{2,3} as an induced minor, then either

{S:S is a minimal separator of G}p(V(G))|\{S:S\text{ is a minimal separator of }G\}|\leq p(|V(G)|)

or GG has no hole of length at least kk.

This proposes a structural dichotomy for graphs excluding K2,3K_{2,3} as an induced minor: graphs without clique cutsets should either have polynomially many minimal separators or have uniformly bounded hole length. The source presents this as an open question; no resolution is given.

Sources & referencesView supporting material

Primary source

Nicolas Bousquet, Clément Dallard, Maël Dumas, Claire Hilaire, Martin Milanič, Anthony Perez and Nicolas Trotignon, “Induced Minor Models. I. Structural Properties and Algorithmic Consequences”, arXiv:2402.08332 (2025).

Additional references

2 papers in this index state this conjecture (2015–2024). The statement above is taken from the most recent of them; the others are arXiv:1504.04821.

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.