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.
References
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
No solutions have been posted yet.