Connectedness conjecture for friends-and-strangers graphs of complete bipartite graphs
Statement
Let be a graph on vertices. A -bridge is a set of edges whose deletion disconnects the graph, and it is non-trivial when neither resulting component is an isolated vertex. The graph is the friends-and-strangers graph associated with the graphs and . Connectedness conjecture. The graph is connected if and only if is a connected non-bipartite graph without a non-trivial -bridge and . This conjecture extends the established disconnectedness criterion, while the cited theorems provide only weaker sufficient conditions for connectedness; the full characterization remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.