Digraph redicolouring
share
Given two k-dicolourings of a digraph D, we prove that it is PSPACE-complete to decide whether we 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. A digraph is said to be k-mixing if there exists a transformation between any pair of k-colourings. We show that every digraph D is k-mixing for all k≥δ^*_min(D)+2, generalizing a result due to Dyer et al. We also prove that every oriented graph G⃗ is k-mixing for all k≥δ^*_max(G⃗) +1 and for all k≥δ^*_ avg(G⃗)+1. We conjecture that, for every digraph D, the dicolouring graph of D on k≥δ_min^*(D)+2 colours has diameter at most O(|V(D)|^2) and give some evidences. We first prove that the dicolouring graph of any digraph D on k≥ 2δ_min^*(D) + 2 colours has linear diameter, extending a result from Bousquet and Perarnau. We also prove that the conjecture is true when k≥3/2(δ_min^*(D)+1). Restricted to the special case of oriented graphs, we prove that the dicolouring graph of any subcubic oriented graph on k≥ 2 colours is connected and has diameter at most 2n. We conjecture that every non 2-mixing oriented graph has maximum average degree at least 4, and we provide some support for this conjecture by proving it on the special case of 2-freezable oriented graphs. More generally, we show that every k-freezable oriented graph on n vertices must contain at least kn + k(k-2) arcs, and we give a family of k-freezable oriented graphs that reach this bound. In the general case, we prove as a partial result that every non 2-mixing oriented graph has maximum average degree at least 7/2.
READ FULL TEXT