Abstract. For a fixed graph [Formula: see text], the [Formula: see text]-Recoloring problem asks whether, given two homomorphisms from a graph [Formula: see text] to [Formula: see text], one homomorphism can be transformed into the other by changing the image of a single vertex in each step and maintaining a homomorphism to [Formula: see text] throughout. The most general algorithmic result for [Formula: see text]-Recoloring so far was proposed by Wrochna in 2014, who introduced a topological approach to obtain a polynomial-time algorithm for any undirected loopless square-free graph [Formula: see text]. We show that the topological approach can be used to recover essentially all previous algorithmic results for [Formula: see text]-Recoloring and that it is applicable also in the more general setting of digraph homomorphisms. In particular, we show that [Formula: see text]-Recoloring admits a polynomial-time algorithm if (i) [Formula: see text] is a loopless digraph that does not contain a 4-cycle of algebraic girth 0 and (ii) [Formula: see text] is a reflexive digraph that contains no triangle of algebraic girth 1 and no 4-cycle of algebraic girth 0. In both cases, we obtain a polynomial-time algorithm for finding shortest transformations.

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 Wrochna in 2014, 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.

We consider the class of graphs that contain no bull, no odd hole, and no antihole of length at least five. We present a new algorithm that colors optimally the vertices of every graph in this class. This algorithm is based on the existence in every such graph of an ordering of the vertices with a special property. More generally we prove, using a variant of lexicographic breadth-first search, that in every graph that contains no bull and no hole of length at least five there is a vertex that is not the middle of a chordless path on five vertices. This latter fact also generalizes known results about chordal bipartite graphs, totally balanced matrices, and strongly chordal graphs.