Determining a graph from its reconfiguration graph

Abstract

Given a graph G and a natural number k , the k -recolouring graph C k ( G ) is the graph whose vertices are the k -colourings of G and whose edges link pairs of colourings which differ at exactly one vertex of G . Recently, Hogan et al. proved that G can be determined from C k ( G ) provided k is large enough (quadratic in the number of vertices of G ). We improve this bound by showing that k = χ ( G ) + 1 colours suffice, and provide examples of families of graphs for which k = χ ( G ) colours do not suffice. We then extend this result to k -Kempe-recolouring graphs, whose vertices are again the k -colourings of a graph G and whose edges link pairs of colourings which differ by swapping the two colours in a connected component of the subgraph induced by selecting those two colours. We show that k = χ ( G ) + 2 colours suffice to determine G in this case. Finally, we investigate the case of independent set reconfiguration, proving that in only a few trivial cases is one guaranteed to be able to determine a graph G . An extended abstract of this paper was presented at EuroComb 2025 [3] .