2014-09-29
10:00-11:00
FAMNIT-SEMIN
Dr Matthew Johnson (Durham University, UK)
Finding (Shortest) Paths between Graph Colourings
The reconfiguration graph of the $k$-colourings of a graph $G$ contains as its vertex set the proper vertex $k$-colourings of $G$, and two colourings are joined by an edge in the reconfiguration graph if they differ in colour on just one vertex of $G$. We investigate the structure of reconfiguration graphs and the computational complexity of recognizing whether or not a pair of colourings belong to the same component of the reconfiguration graph (that is, the complexity of deciding if it is possible to transform one colouring into another with a sequence of ”recolouring” steps that each change the colour on just one vertex without ever breaking the constraint that neighbours are not coloured alike).
We can similarly define the reconfiguration graph (or solution graph) of an instance of any search problem – the vertex set is the set of all possible solutions and the edge relation describes when a pair of distinct solutions have minimum difference (in some sense). We review research into these graphs with a focus on our recent work on shortest paths (in the reconfiguration graph) between graph colourings.
Joint work with Dieter Kratsch, Stefan Kratsch, Viresh Patel and Daniël Paulusma.