Dichotomy for bounded degree H-colouring

Given a graph H, let b (H) be the minimum integer b, if it exists, for which H-colouring is N P-complete when restricted to instances with degree bounded by b. We show that b (H) exists for any non-bipartite graph. This verifies for graphs the conjecture of Feder, Hell, and Huang that any CSP that is N P-complete, is N P-complete for instances of some maximum degree. Furthermore, we show the same for all projective CSPs, and we get constant upper bounds on the parameter b for various infinite classes of graph. For example, we show that b (H) = 3 for any graph H with girth at least 7 in which every edge lies in a g-cycle, where g is the odd-girth of H.