Summary: For a fixed graph \(H\), the \(H\)-Recoloring problem asks whether, given two homomorphisms from a graph \(G\) to \(H\), one homomorphism can be transformed into the other by changing the image of a single vertex in each step and maintaining a homomorphism to \(H\) throughout. The most general algorithmic result for \(H\)-Recoloring so far has been proposed by M. Wrochna [“Homomorphism reconfiguration via homotopy”, SIAM J. Discrete Math. 34, No. 1, 328–350, 2020. doi:10.1137/17M1122578], who introduced a topological approach to obtain a polynomial-time algorithm for any undirected loopless square-free graph \(H\). We show that the topological approach can be used to recover essentially all previous algorithmic results for \(H\)-Recoloring and that it is applicable also in the more general setting of digraph homomorphisms. In particular, we show that \(H\)-Recoloring admits a polynomial-time algorithm i) if \(H\) is a loopless digraph that does not contain a 4-cycle of algebraic girth 0 and ii) if \(H\) is a reflexive digraph that contains no triangle of algebraic girth 1 and no 4-cycle of algebraic girth 0.
For the entire collection see [Zbl 1507.68023].