30 September 2022 to 1 October 2022
Asia/Seoul timezone

Reconfiguration of homomorphism extensions

30 Sept 2022, 14:55
20m

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)

Presentation materials

There are no materials yet.