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

$k$-freezable oriented graphdicolouringoriented digraphsrecolouringsubcubic oriented graph

Mathematics Subject Classification ID

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

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

Review text

The authors extend several known tough results concerning dicoloring of graphs and also raise some new conjectures. First, they establish that given two $k$-dicolourings of a digraph $D$, it is PSPACE-complete to decide whether one 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. They pose a new conjecture which is an analogue of Cereceda's conjecture for digraphs [\textit{L. Cereceda}, Mixing graph colourings. London: London School of Economics and Political Science (PhD Thesis) (2007)] and generalized it to digraphs with two new results supporting Cereceda's conjecture. Further, for the restricted version of oriented graphs, they prove that the dicolouring graph of any subcubic oriented graph on $k\geq 2$ colours is connected and has diameter at most $2n$. They also raise an open conjecture namely ``every non-2-mixing oriented graph has a maximum average degree of at least 4 to the graph theory community by proving it for the special case of 2-freezable oriented graphs. They also show that every $k$-freezable oriented graph on \(n\) vertices must contain at least $kn + k(k-2)$ arcs and a family of $k$-freezable oriented graphs that reach this bound. For the general case, they prove a partial result that every non-2-mixing oriented graph has maximum average degree of at least 7.2.

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 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• 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

(3)

• Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• Brooks-type colourings of digraphs in linear time

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)