Polynomial minimal separators or bounded hole length for induced-minor-free graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.