Graph homomorphisms with infinite targets

AbstractLet H be a fixed graph whose vertices are called colours. Informally, an H-colouring of a graph G is an assignment of these colours to the vertices of G such that adjacent vertices receive adjacent colours. We introduce a new tool for proving NP-completeness of H-colouring problems, which unifies all methods used previously. As an application we extend, to infinite graphs of bounded degree, the theorem of Hell and Nešetřil that classifies finite H-colouring problems by complexity