Digraph redicolouring

DOI10.1016/J.EJC.2023.103876MaRDI QIDQ6146501zbMATH OpenFDO

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)

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

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)

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$.

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

Cites work

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

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)