2025/04/28 by Gaétan Berthe, Berthe, Gaétan, Caroline Brosse +9 · 1 citation
Computer Science · Mathematics · #Graph Theory and Algorithms #Graph theory and applications #Interconnection Networks and Systems #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2504.19783
openalex publication_date 2025/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
Given a graph G and a natural number k, the k-recolouring graph Ck(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 Ck(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.