The biconnected friends-and-strangers connectivity conjecture

Let YY be a graph on n3n\geq 3 vertices such that its complement is a forest consisting of trees T1,,Tr\mathcal T_1,\dots,\mathcal T_r with

gcd(V(T1),,V(Tr))=1.\gcd\bigl(|V(\mathcal T_1)|,\dots,|V(\mathcal T_r)|\bigr)=1.

If XX is a biconnected graph on nn vertices, the biconnected connectivity conjecture asserts that FS(X,Y)\mathsf{FS}(X,Y) is connected. This generalizes the known characterization for X=CyclenX=\textsf{Cycle}_n to all biconnected graphs and is attributed in the source to Defant et al.; it remains open in the supplied text.

Sources & referencesView supporting material

Primary source

Ryan Jeong, “On the Diameters of Friends-and-Strangers Graphs”, arXiv:2201.00665 (2023).

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.