Digraph redicolouring
From MaRDI portal
Publication:6146501
DOI10.1016/j.ejc.2023.103876arXiv2301.03417MaRDI QIDQ6146501
Nicolas Nisse, Nicolas Bousquet, L. Picasarri-Arrieta, Amadeus Reinald, Frédéric Havet
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
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Fast recoloring of sparse graphs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- Frozen colourings of bounded degree graphs
- The dichromatic number of a digraph
- Explicit construction of graphs with an arbitrary large girth and of large size
- A polynomial version of Cereceda's conjecture
- Introduction to reconfiguration
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The complexity of change
- Finding paths between 3-colorings
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
This page was built for publication: Digraph redicolouring