The theta-pyramid-prism-turtle minimal separator conjecture
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 such that every graph that contains no theta, pyramid, prism, or turtle has at most 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.