Graph-theory open problems

Polynomial minimal separators in odd-hole-free graphs

Open problem: polynomial separator property for (prism, pyramid, theta, even wheel)-free graphs · arXiv:1912.11246

arXiv Informal medium confidence— first stated 2019-12-24
Authors: Maria Chudnovsky, Stéphan Thomassé, Nicolas Trotignon, Kristina Vušković

Status solved high confidence

Every turtle contains an induced even wheel, so the cited n^18 bound for (theta, pyramid, prism, turtle)-free graphs applies directly.

Cited literature (1)

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: This uses the standard adjacent-centers definition of a turtle from arXiv:2005.05042 and the theorem quoted in the prompt.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

Informal. It is unknown whether (prism, pyramid, theta, even wheel)-free graphs have polynomially many minimal separators.

Context

The authors note that a weakening of Conjecture 2.2 is obtained by restricting to (prism, pyramid, theta, even wheel)-free graphs (since prisms, thetas, and turtles all contain even holes). They explicitly state they 'were not able to prove that (prism, pyramid, theta, even wheel)-free graphs have polynomially many minimal separators,' which is why the main result (Theorem 2.3) additionally excludes squares.

Notes. Implicit open problem arising from the gap between Conjecture 2.2 and Theorem 2.3; not labeled as a formal conjecture or problem in the paper.

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