Polynomial minimal separators in (prism,pyramid,theta,turtle)-free graphs

Conjecture 2.2 · arXiv:1912.11246

arXiv Conjecture high confidence— first stated 2019-12-24

Authors: Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković

Status solved high confidence

Conjecture 2.2 from arXiv:1912.11246 was proved in full by Abrishami, Chudnovsky, Dibek, Thomassé, Trotignon, and Vušković in arXiv:2005.05042. Their Theorem 1.2 establishes that every (theta, pyramid, prism, turtle)-free graph G has at most |V(G)|^18 minimal separators, constructible in polynomial time. The result is optimal in the sense that excluding only three of the four forbidden subgraphs still permits exponentially many minimal separators.

Cited literature (1)

proof Graphs with polynomially many minimal separators (2022)

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković · Journal of Combinatorial Theory, Series B · arXiv:2005.05042 · doi:10.1016/j.jctb.2021.10.003

Proves the conjecture in full (as Theorem 1.2): every (theta, pyramid, prism, turtle)-free graph G has at most |V(G)|^18 minimal separators, constructible in polynomial time, and as a consequence gives a polynomial-time algorithm for maximum weight independent set in this class.

Reviewer notes. The conjecture was stated as Conjecture 2.2 in arXiv:1912.11246 and is restated as Conjecture 1.1 in the follow-up paper arXiv:2005.05042, where it is proved as Theorem 1.2. The bound |V(G)|^18 is explicit. The result is tight: for any subset of three of the four forbidden patterns there exist graphs with exponentially many minimal separators.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. There is a polynomial $P$ such that every graph $G$ that contains no prism, pyramid, theta or turtle has at most $P(|V(G)|)$ minimal separators.

Context

The authors survey families of graphs with exponentially many minimal separators (k-prisms, k-pyramids, k-thetas, k-turtles, k-ladders) and observe that every known such example contains a prism, pyramid, theta, or turtle. They propose Conjecture 2.2 as 'in some sense the best possible statement regarding bounding the number of minimal separators.' The paper proves a weaker result (Theorem 2.3) for the class $\mathcal{C}$ of (square, prism, pyramid, theta, even wheel)-free graphs.

Source paper

Maximum independent sets in (pyramid, even hole)-free graphs
Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković · 2019-12-24
https://arxiv.org/abs/1912.11246 PDF source