A Brightwell-Winkler type characterisation of NU graphs

Abstract

In 2000, Brightwell and Winkler characterised dismantlable graphs as the graphs $H$ for which the Hom-graph $\mathrm{Hom}(G,H)$, defined on the set of homomorphisms from $G$ to $H$, is connected for all graphs $G$. This shows that the reconfiguration version $\mathrm{Reco}{\mathrm{n}}_{\mathrm{Hom}}(H)$ of the $H$-colouring problem, in which one must decide for a given $G$ whether $\mathrm{Hom}(G,H)$ is connected, is trivial if and only if $H$ is dismantlable. We prove a similar starting point for the reconfiguration version of the $H$-extension problem. Where $\mathrm{Hom}(G,H;p)$ is the subgraph of the Hom-graph $\mathrm{Hom}(G,H)$ induced by the $H$-colourings extending the $H$-precolouring $p$ of $G$, the reconfiguration version $\mathrm{Reco}{\mathrm{n}}_{\mathrm{Ext}}(\mathrm{H})$ of the $H$-extension problem asks, for a given $H$-precolouring $p$ of a graph $G$, if $\mathrm{Hom}(G,H;p)$ is connected. We show that the graphs $H$ for which $\mathrm{Hom}(G,H;p)$ is connected for every choice of $(G,p)$ are exactly the $\mathrm{NU}$ graphs. This gives a new characterisation of $\mathrm{NU}$ graphs, a nice class of graphs that is important in the algebraic approach to the $\mathrm{CSP}$-dichotomy. We further give bounds on the diameter of $\mathrm{Hom}(G,H;p)$ for $\mathrm{NU}$ graphs $H$, and show that shortest path between two vertices of $\mathrm{Hom}(G,H;p)$ can be found in parameterised polynomial time. We apply our results to the problem of shortest path reconfiguration, significantly extending recent results.

arXiv comment17 pages, 1 figure