Digraph redicolouring - INRIA - Institut National de Recherche en Informatique et en Automatique Access content directly
Journal Articles European Journal of Combinatorics Year : 2024

Digraph redicolouring


In this work, we generalize several results on graph recolouring to digraphs. 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-dicolourings. 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. Here δ * min , δ * max , and δ * avg denote the min-degeneracy, the max-degeneracy, and the average-degeneracy respectively. We pose as a 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). This is the analogue of Cereceda's conjecture for digraphs. We generalize to digraphs two results supporting Cereceda's conjecture. 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 analogue of Cereceda's conjecture is true when k ≥ 3 2 (δ * min (D) + 1), which generalizes a result from Bousquet and Heinrich. 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 .
Fichier principal
Vignette du fichier
Dicolouring_reconfiguration_article-5.pdf (438.26 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04306893 , version 1 (25-11-2023)



Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta, Amadeus Reinald. Digraph redicolouring. European Journal of Combinatorics, 2024, 116, pp.103876. ⟨10.1016/j.ejc.2023.103876⟩. ⟨hal-04306893⟩
118 View
18 Download



Gmail Facebook X LinkedIn More