2023/01/09 by Bousquet, Nicolas, Havet, Frédéric, Nisse, Nicolas +2
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2301.03417
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≥ δ^*\rm 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).