Summary: Given digraphs \(G\) and \(H\), the colouring graph \(\mathrm{Col}(G, H)\) has as its vertices all homomorphism of \(G\) to \(H\). There is an arc \(\phi \rightarrow \phi^\prime\) between two homomorphisms if they differ on exactly one vertex \(v\), and if \(v\) has a loop we also require \(\phi(v) \rightarrow \phi^\prime(v)\). The recolouring problem asks if there is a path in \(\mathrm{Col}(G, H)\) between given homomorphisms \(\phi\) and \(\psi\). We examine this problem in the case where \(G\) is a digraph and \(H\) is a reflexive, digraph cycle.
We show that for a reflexive digraph cycle \(H\) and a reflexive digraph \(G\), the problem of determining whether there is a path between two maps in \(\mathrm{Col}(G, H)\) can be solved in time polynomial in \(G\). When \(G\) is not reflexive, we show the same except for certain digraph 4-cycles \(H\).