Bangachev's minimum-degree conjecture for friends-and-strangers graphs

Let XX and YY be connected graphs on nn vertices. For a graph GG, write δ(G)\delta(G) for its minimum degree, and let FS(X,Y)\operatorname{FS}(X,Y) denote the friends-and-strangers graph of XX and YY. Bangachev's conjecture. If

2min(δ(X),δ(Y))+3max(δ(X),δ(Y))3n,2\min(\delta(X),\delta(Y))+3\max(\delta(X),\delta(Y))\geq 3n,

then FS(X,Y)\operatorname{FS}(X,Y) is connected. This conjecture concerns minimum-degree conditions guaranteeing connectedness of friends-and-strangers graphs; the supplied text attributes it to Bangachev but gives no evidence of resolution.

Sources & referencesView supporting material

Primary source

Xinghui Zhao, Lihua You, Jifu Lin and Xiaoxue Zhang, “The connectedness of friends-and-strangers graphs about graph parameters and others”, arXiv:2504.00373 (2025).

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.