Digraph redicolouring

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

zbMATH Keywords

recolouring$k$-freezable oriented graphdicolouringoriented digraphssubcubic oriented graph

Mathematics Subject Classification ID

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