Graph Homomorphism Reconfiguration and Frozen $H$-Colourings
Richard C. Brewster, Jae-baek Lee, Benjamin R. Moore, Jonathan A. Noel, Mark Siggers · arXiv (Cornell University) · 2017
For a fixed graph $H$, the reconfiguration problem for $H$-colourings (i.e. homomorphisms to $H$) asks: given a graph $G$ and two $H$-colourings $φ$ and $ψ$ of $G$, does there exist a sequence $f_0,\dots,f_m$ of $H$-colourings such that $f_0=φ$, $f_m=ψ$ and $f_i(u)f_{i+1}(v)\in E(H)$ for every $0\leq i