On the complexity of H-coloring (Q1100215)

In standard graph colouring adjacent vertices are required to have different colours. If the set of colours itself forms a graph H, then in an H-colouring of G adjacent vertices are required to have adjacent colours. (Thus an H-colouring of G is just a homomorphism of G to H.) The complexity of deciding the H-colourability of an input graph depends on H. For instances, when H is a complete graph with at least three vertices then H-colourability is NP-complete because it is the traditional colourability problem. When H is bipartite, then H-colourability is equivalent to bipartiteness, and so can be decided in polynomial time. The authors prove that H-colourability is NP-complete in all other cases. That this was the case was a conjecture of Maurer, Sudborough, and Welzl, popularized in one of David Johnson's NP-completeness columns. It is often not difficult to prove the NP-completeness of H-colouring for particular classes of graphs H, and several such results exist in the literature. The proof of the full conjecture given here is interesting because of the intricate interplay of the various basic reductions and the complex graphs that are employed in them.