The theta-pyramid-prism-turtle minimal separator conjecture

A graph is a finite undirected graph, and a minimal separator is a vertex set that minimally separates some pair of vertices. Theta-pyramid-prism-turtle conjecture. There is a polynomial PP such that every graph GG that contains no theta, pyramid, prism, or turtle has at most P(V(G))P(|V(G)|) minimal separators. This conjecture asks whether forbidding these four graph configurations guarantees polynomially many minimal separators; the paper presents it as a conjecture from the cited work, and its status is not resolved here.

Sources & referencesView supporting material

Primary source

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon and Kristina Vušković, “Graphs with polynomially many minimal separators”, arXiv:2005.05042 (2021).

Additional references

2 papers in this index state this conjecture (2019–2020). The statement above is taken from the most recent of them; the others are arXiv:1912.11246.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.