The coprime forest conjecture for friends-and-strangers graphs
The coprime forest conjecture for friends-and-strangers graphs
Let and be graphs on vertices. A graph is biconnected if it is connected and has no cut vertex. Write for the complement of , and let denote the friends-and-strangers graph associated to and . Suppose that
is a forest whose components are trees, with
Coprime forest conjecture. If is biconnected, then is connected.
This conjecture asserts that the necessary condition obtained from the cycle case is also sufficient for every biconnected graph . The paper verifies the property for several choices of , including when the complement is a tree on vertices together with an isolated vertex, but the general assertion is left open.
Sources & referencesView supporting material
Primary source
Colin Defant and Noah Kravitz, “Friends and Strangers Walking on Graphs”, arXiv:2009.05040 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.