Digraph redicolouring (Q6146501)

The authors extend several known tough results concerning dicoloring of graphs and also raise some new conjectures. First, they establish that given two $k$-dicolourings of a digraph $D$, it is PSPACE-complete to decide whether one can transform one into the other by recolouring one vertex at each step while maintaining a dicolouring at any step even for $k=2$ and for digraphs with maximum degree 5 or oriented planar graphs with maximum degree 6. They pose a new conjecture which is an analogue of Cereceda's conjecture for digraphs [\textit{L. Cereceda}, Mixing graph colourings. London: London School of Economics and Political Science (PhD Thesis) (2007)] and generalized it to digraphs with two new results supporting Cereceda's conjecture. Further, for the restricted version of oriented graphs, they prove that the dicolouring graph of any subcubic oriented graph on $k\geq 2$ colours is connected and has diameter at most $2n$. They also raise an open conjecture namely ``every non-2-mixing oriented graph has a maximum average degree of at least 4'' to the graph theory community by proving it for the special case of 2-freezable oriented graphs. They also show that every $k$-freezable oriented graph on \(n\) vertices must contain at least $kn + k(k-2)$ arcs and a family of $k$-freezable oriented graphs that reach this bound. For the general case, they prove a partial result that every non-2-mixing oriented graph has maximum average degree of at least 7.2.