Digraph redicolouring

DOI10.1016/J.EJC.2023.103876arXiv2301.03417MaRDI QIDQ6146501FDOQ6146501

Authors: Nicolas Bousquet, Frédéric Havet, Nicolas Nisse, L. Picasarri-Arrieta, Amadeus Reinald 

Publication date: 5 February 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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 $kgeqdelt{a}_{min}^{\ast }(D)+2$, generalizing a result due to Dyer et al. We also prove that every oriented graph $vecG$ is $k$-mixing for all $kgeqdelt{a}_{max}^{\ast }(vecG)+1$ and for all $kgeqdelt{a}_{mavg}^{\ast }(vecG)+1$. We conjecture that, for every digraph $D$, the dicolouring graph of $D$ on $kgeqdelt{a}_{min}^{\ast }(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 $kgeq2delt{a}_{min}^{\ast }(D)+2$ colours has linear diameter, extending a result from Bousquet and Perarnau. We also prove that the conjecture is true when $kgeqfrac32(delt{a}_{min}^{\ast }(D)+1)$. Restricted to the special case of oriented graphs, we prove that the dicolouring graph of any subcubic oriented graph on $kgeq2$ 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 $frac72$.

Full work available at URL: https://arxiv.org/abs/2301.03417

Recommendations

• Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• A polynomial version of Cereceda's conjecture
• Colouring non-even digraphs

zbMATH Keywords

recolouring$k$-freezable oriented graphdicolouringoriented digraphssubcubic oriented graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Mixing 3-colourings in bipartite graphs
• The dichromatic number of a digraph
• The complexity of change
• Finding paths between 3-colorings
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Explicit construction of graphs with an arbitrary large girth and of large size
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• A polynomial version of Cereceda's conjecture
• Introduction to reconfiguration
• Fast recoloring of sparse graphs
• Frozen colourings of bounded degree graphs

Cited In (2)

• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring

This page was built for publication: Digraph redicolouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6146501)