Undecidable Generalized Colouring Problems

Abstract

Let $H$ be a graph. An $H$-colouring of a graph $G$ is an edge-preserving mapping of the vertices of $G$ to the vertices of $H$. We consider the Extendable $H$-colouring Problem, that is, the problem of deciding whether a partial $H$-colouring of some finite subset of the vertices of $G$ can be extended to an $H$-colouring of $G$. We show that, for a class of finitely described infinite graphs, Extendable $H$-colouring is undecidable for all finite non-bipartite graphs $H$, and also for some finite bipartite graphs $H$. Similar results are established when $H$ is a finite reflexive graph.