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

About 11 years old · traced to

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.

References

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.