Reconfiguration is concerned with relationships among solutions to a problem instance,
where the reconfiguration of one solution to another is a sequence of steps such that each …

Let k be an integer. Two vertex k-colorings of a graph are adjacent if they differ on exactly
one vertex. A graph is k-mixing if any proper k-coloring can be transformed into any other …

Let G be a graph with a vertex colouring α. Let a and b be two colours. Then a connected
component of the subgraph induced by those vertices coloured either a or b is known as a …

Let k and d be positive integers such that k≥ d+ 2. Consider two k-colourings of a d-
degenerate graph G. Can we transform one into the other by recolouring one vertex at each …

Let G be a simple undirected connected graph on n vertices with maximum degree Δ.
Brooks' Theorem states that G has a proper Δ‐coloring unless G is a complete graph, or a …

For a positive integer, the-recoloring graph of a graph has as vertex set all proper-colorings
of with two-colorings being adjacent if they differ by the color of exactly one vertex. A result of …

Given a graph G=(V, E) and a proper vertex colouring of G, a Kempe chain is a subset of V
that induces a maximal connected subgraph of G in which every vertex has one of two …

The reconfiguration graph R k (G) for the k-colorings of a graph G has as vertex set the set of
all possible k-colorings of G and two colorings are adjacent if they differ in the color of …

In this work, we generalize several results on graph recolouring to digraphs. Given two k-
dicolourings of a digraph D, we prove that it is PSPACE-complete to decide whether we can …

The reconfiguration graph R k (G) for the k-colorings of a graph G has as vertices all
possible k-colorings of G and two colorings are adjacent if they differ in the color of exactly …