  We say that a graph is $k$-mixing if it is possible to transform any
$k$-coloring into any other via a sequence of single vertex recolorings keeping
a proper coloring all along. Cereceda, van den Heuvel and Johnson proved that
deciding if a graph is $3$-mixing is co-NP-complete and left open the case $k
\ge 4$. We prove that for every $k \ge 4$, $k$-mixing is co-NP-hard.
