Polynomial minimal separators or bounded hole length for induced-minor-free graphs
Let be a graph. A clique cutset is a clique whose deletion disconnects , a minimal separator is a minimal vertex set separating two vertices of , and a hole is an induced cycle of length at least four. An induced minor of is obtained by deleting vertices and contracting edges.
Polynomial-separator or bounded-hole conjecture. There exists a polynomial and an integer such that if has no clique cutset and does not contain as an induced minor, then either
or has no hole of length at least .
This proposes a structural dichotomy for graphs excluding 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
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.