Dichotomy for bounded degree HH-colouring

Given a graph HH, let b(H)b(H) be the minimum integer bb, if it exists, for which HH-colouring is NPNP-complete when restricted to instances with degree bounded by bb. We show that b(H)b(H) exists for any non-bipartite graph. This verifies for graphs the conjecture of Feder, Hell, and Huang that any CSP that is NPNP-complete, is NPNP-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 bb for various infinite classes of graph. For example, we show that b(H)=3b(H)=3 for any graph HH with girth at least 7 in which every edge lies in a gg-cycle, where gg is the odd-girth of HH.