The k-creature minimal separator conjecture

At least 5 years old · documented by

For an integer k≥3k \geq 3, a graph GG is a kk-creature if

V(G)=A∪B∪x1,…,xk∪y1,…,ykV(G)=A\cup B\cup\\{x_1,\dots,x_k\\}\cup\\{y_1,\dots,y_k\\}

such that G[A]G[A] and G[B]G[B] are connected, AA is anticomplete to BB, for i=1,…,ki=1,\dots,k, xiyi∈E(G)x_i y_i\in E(G), xix_i has a neighbor in AA and is anticomplete to BB, yiy_i has a neighbor in BB and is anticomplete to AA, and for 1≤i,j≤k1\leq i,j\leq k with i≠ji\ne j, xiyj∉E(G)x_i y_j\notin E(G). A minimal separator is a vertex set that minimally separates some pair of vertices. kk-creature conjecture. There exists f:N→Nf:\mathbb{N}\to\mathbb{N} such that if no induced subgraph of GG is a kk-creature, then GG has at most ∣V(G)∣f(k)|V(G)|^{f(k)} minimal separators. This is proposed as a stronger version of the paper's main theorem: excluding induced kk-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

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.