The Complexity of Bounded Length Graph Recoloring

Paul Bonsma, Amer E. Mouawad

We study the following question: Given are two $k$-colorings $\alpha$ and $\beta$ of a graph $G$ on $n$ vertices, and integer $\ell$. The question is whether $\alpha$ can be modified into $\beta$, b…