In the k-recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. In this talk, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of the digraph, showing that the problem is solvable in linear time when the digraph is a directed cycle or is in a class of multitrees. This talk is based on joint work with Soichiro Fujii, Yuni Iwamasa, and Akira Suzuki.