Redicolouring digraphs: directed treewidth and cycle-degeneracy

DOI10.1016/j.dam.2024.05.042zbMATH Open1544.0504MaRDI QIDQ6585259

Ignasi Sau, Nicolas Nisse, L. Picasarri-Arrieta

Publication date: 9 August 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

directed graphsreconfigurationdichromatic numbergraph recolouringdirected decompositions

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• The dag-width of directed graphs
• Fast recoloring of sparse graphs
• Digraph measures: Kelly decompositions, games, and orderings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Recoloring graphs via tree decompositions
• The dichromatic number of a digraph
• Directed tree-width
• A Thomassen-type method for planar graph recoloring
• A polynomial version of Cereceda's conjecture
• The digrundy number of digraphs
• Reconfiguring colorings of graphs with bounded maximum average degree
• An update on reconfiguring 10-colorings of planar graphs
• Introduction to reconfiguration
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
• 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
• Mathematical Foundations of Computer Science 2005
• Digraphs
• Recoloring Planar Graphs of Girth at Least Five
• Digraph redicolouring
• Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring

This page was built for publication: Redicolouring digraphs: directed treewidth and cycle-degeneracy