Polynomial minimal separators via k-creature exclusion

Conjecture 1.4 · arXiv:2005.05042

arXiv Conjecture high confidence— first stated 2021-12-28

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

Status disproved medium confidence

Conjecture 1.4 was disproved by Gartland and Lokshtanov (arXiv:2007.08761, posted July 2020), who exhibited a counterexample showing that forbidding k-creatures for a fixed k does not suffice to guarantee polynomially many minimal separators. Their paper proves instead the weaker result that hereditary classes excluding k-creatures are 'strongly quasi-tame' (quasi-polynomially many minimal separators) under an additional condition that minimal separators can be dominated by a bounded number of vertices. Related SODA 2023 work showed that forbidding both k-creatures and k-critters yields a quasi-polynomial separator bound.

Cited literature (1)

counterexample Dominated Minimal Separators are Tame (Nearly All Others are Feral) (2020)

Peter Gartland, Daniel Lokshtanov · arXiv preprint · arXiv:2007.08761

Provides an explicit counterexample to the conjecture that every hereditary class excluding k-creatures for fixed k has polynomially many minimal separators, and in its place proves that such classes are strongly quasi-tame when minimal separators can be dominated by a fixed number of vertices.

Reviewer notes. The counterexample in arXiv:2007.08761 was posted July 2020, two months after the source arXiv preprint (May 2020) and over a year before its journal publication (December 2021); it is included in since_posted because it postdates the conjecture's first public statement. SODA 2023 companion papers 'Graph Classes with Few Minimal Separators I & II' prove a dichotomy result and show quasi-polynomial bounds for graphs excluding both k-creatures and k-critters, but their arXiv IDs were not verified within the web-call budget. arXiv:2405.15543 (2024) continues this line of work with a tame vs. feral dichotomy for graphs excluding an induced minor or topological minor, but its direct bearing on Conjecture 1.4 was not verified.

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

Conjecture. There exists $f : \mathbb{N} \to \mathbb{N}$ such that if no induced subgraph of $G$ is a $k$-creature, then $G$ has at most $|V(G)|^{f(k)}$ minimal separators.

Context

A $k$-creature is a graph whose vertex set partitions into sets $A, B, \{x_1,\ldots,x_k\}, \{y_1,\ldots,y_k\}$ satisfying connectivity, anticomplete, and matching conditions; every $k$-creature contains a theta, pyramid, prism, or turtle. The authors propose this as a stronger generalisation of Theorem 1.2, noting that even if true it does not fully characterise classes with the polynomial separator property (the class $\mathcal{D}$ of induced subgraphs of $k$-turtles with very long paths has the polynomial separator property yet contains $k$-creatures of arbitrarily large $k$).

Notes. The paper proves a weaker version (Theorem 1.5) replacing $k$-creatures by the stricter notion of immature $k$-creatures.

Source paper

Graphs with polynomially many minimal separators
Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković · 2021-12-28
https://arxiv.org/abs/2005.05042 PDF source