Polynomial minimal separators in odd-hole-free graphs
Open problem: polynomial separator property for (prism, pyramid, theta, even wheel)-free graphs · arXiv:1912.11246
Status partial medium confidence
The open problem of whether (prism, pyramid, theta, even wheel)-free graphs have polynomially many minimal separators remains unresolved as stated. Abrishami, Chudnovsky, Dibek, Thomassé, Trotignon, and Vušković (arXiv:2005.05042, 2020) proved the closely related result that (theta, pyramid, prism, turtle)-free graphs have at most $|V(G)|^{18}$ minimal separators constructible in polynomial time; this shares three of the four forbidden subgraphs with the open problem but uses turtle in place of even wheel. Whether this result implies the even-wheel-free case (via class inclusion) could not be determined from the abstract alone, leaving the exact conjecture from arXiv:1912.11246 open or at most partially addressed.
Cited literature (1)
-
Proves that (theta, pyramid, prism, turtle)-free graphs have at most $|V(G)|^{18}$ minimal separators, a polynomial bound for a four-forbidden-subgraph class that shares prism, pyramid, and theta with the open problem but replaces even wheel with turtle.
Reviewer notes. The fourth forbidden subgraph differs between the proved result (turtle, in 2005.05042) and the open problem (even wheel, in 1912.11246). Since turtles contain even holes but even wheels may not contain turtles (and vice versa), the two graph classes are likely incomparable, so 2005.05042 does not directly resolve the stated open problem. The published version of 2005.05042 appears in JCTB (ScienceDirect pii S0095895621000848); DOI not verified. No further follow-up specifically addressing the even-wheel-free case was found within the 5-call cap.
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