Skip to main content

Recolouring and homomorphism reconfiguration

Marcin Wrochna ( University of Oxford )

Reconfiguration is the study of how one can move between solutions of a combinatorial problem with small steps. For example, in k-Recolouring, given a graph and two (proper) k-colourings of it, the question is whether one can be reached from the other by changing the colour of one vertex at a time (keeping a proper colouring). The problem is hard for every k>=4, but surprisingly it admits a polynomial algorithm for k=3, as proved by Cereceda, van den Heuvel, and Johnson in 2011. The question generalizes naturally to other constraint satisfaction problems and in particular H-colourings (homomorphisms into a fixed graph H). I will sketch how topological ideas can be used to show that the problem is solvable for any square-free graph H, generalizing the result for 3-colourings. I will also mention the question of whether a dichotomy holds, and a curious relation to Hedetniemi's conjecture on colouring graph products.

 

 

Share this: