Finding Shortest Paths between Graph Colourings

Matthew Johnson, Dieter Kratsch, Stefan Kratsch +2

The $k$-colouring reconfiguration problem asks whether, for a given graph $G$, two proper $k$-colourings $\alpha$ and $\beta$ of $G$, and a positive integer $\ell$, there exists a sequence…