GRAPH HOMOMORPHISMS WITH INFINITE TARGETS

Let 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 v ertices of G such that adjacent vertices receive adjacent colours. We introduce a new tool for proving NP-completeness of H-colouring proble ms, which unifies all methods used previously. As an application we ex tend, to infinite graphs of bounded degree, the theorem of Hell and Ne setril that classifies finite H-colouring problems by complexity.