Speaker
Mark Siggers
(Kyungpook National University)
Description
For a graph H the reconfiguration/mixing versions of the extension problem for H asks, of a given graph G with a partial H-colouring p, if one can move between different homomorphisms extending p, by changing the image of one vertex at a time.
We characterise the graphs H for which one can do so for any choice of G and p and any pair of homomorphsims extending p.
We also consider the number of changes one must make, and apply the result to the shortest path reconfiguration problem.
Primary author
Mark Siggers
(Kyungpook National University)
