The k-creature minimal separator conjecture

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

V(G)=ABx1,,xky1,,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, xiyiE(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 1i,jk1\leq i,j\leq k with iji\ne j, xiyjE(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:NNf:\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.

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

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.