Dichotomy for bounded degree H H -colouring
Given a graph H H , let b(H) b ( H ) be the minimum integer b b , if it exists, for which H H -colouring is NP N P -complete when restricted to instances with degree bounded by b b . 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 NP N P -complete, is NP N P -complete for instances of some maximum degree. Furthermore, we show the same for all projective CSP s, and we get constant upper bounds on the parameter b b for various infinite classes of graph. For example, we show that b(H)=3 b ( H ) = 3 for any graph H H with girth at least 7 in which every edge lies in a g g -cycle, where g g is the odd-girth of H H .
dichotomy constraint satisfaction problem graph colouring bounded degree restriction