Sharp Bounds on Lengths of Linear Recolouring Sequences
Stijn Cambie (Katholieke Universiteit Leuven)
Wouter Cames Van Batenburg (TU Delft - Discrete Mathematics and Optimization)
Daniel W. Cranston (Virginia Commonwealth University)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
A recolouring sequence, between k-colourings α and β of a graph G, transforms α into β by recolouring one vertex at a time, such that after each recolouring step we again have a proper k-colouring of G. The diameter of the k-recolouring graph, diam Ck(G), is the maximum over all pairs α and β of the minimum length of a recolouring sequence from α to β. Much previous work has focused on determining the asymptotics of diam Ck(G): Is it Θ(|G|)? Is it Θ(|G|2)? Or even larger? Here we focus on graphs for which diam Ck(G) = Θ(|G|), and seek to determine more precisely the multiplicative constant implicit in the Θ. In particular, for each k ≥ 3, for all positive integers p and q we exactly determine diam Ck(Kp,q), up to a small additive constant. We also sharpen a recolouring lemma that has been used in multiple papers, proving an optimal version. This improves the multiplicative constant in various prior results. Finally, we investigate plausible relationships between similar reconfiguration graphs.
help_outline