The k-creature minimal separator conjecture
The k-creature minimal separator conjecture
For an integer , a graph is a -creature if
such that and are connected, is anticomplete to , for , , has a neighbor in and is anticomplete to , has a neighbor in and is anticomplete to , and for with , . A minimal separator is a vertex set that minimally separates some pair of vertices. -creature conjecture. There exists such that if no induced subgraph of is a -creature, then has at most minimal separators. This is proposed as a stronger version of the paper's main theorem: excluding induced -creatures is conjectured to imply a polynomial bound on minimal separators, but the source provides no resolution.
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).
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.