Answers are grounded in this paper and cite their sources.
Given a graph G and an integer k, the reconfiguration graph Rₖ(G) has the proper k-colourings of G for vertices, two of which are adjacent if and only if they differ on precisely one vertex of G. In $2022$, Cambie, Cranston and the author proved that the diameter of RΔ+2(G) is at most $n+2μ$, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of RΔ+2(G) is precisely equal to $n + μ$, for every graph G with n vertices, matching number $μ$ and maximum degree $Δ$. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least n+3/2μ-2. We also provide counterexamples that are $Δ$-regular, we show that every graph has reconfiguration diameter at least n+1/2 μ, and we advertise an extension to hypergraphs. It is now much more mysterious how the diameter behaves, so we propose a number of open problems.
No takes yet. Share an insight, caveat, or question.
Wouter Cames van Batenburg (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: