Undecidable Generalized Colouring Problems

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.