Jonathan Noel

Reconfiguring Graph Colourings and Homomorphisms

The reconfiguration problem for graph colourings asks, given two proper k-colourings f and g of a graph G, is it possible to transform f into g by performing a sequence of single-vertex recolourings such that every intermediate mapping is a proper k-colouring? We consider a generalisation of this problem to graph homomorphisms. A homomorphism from a graph G to a graph H, also known as an H-colouring, is a mapping from V(G) to V(H) which preserves adjacency. Proper graph colourings can be seen as H-colourings where H is a clique. In this talk, we will discuss some recent results on the computational complexity of the reconfiguration problem for H-colourings and other related problems and mention a number of conjectures and open questions.