Dichotomy for bounded degree -colouring

Abstract: Given a graph , let be the minimum integer , if it exists, for which -colouring is -complete when restricted to instances with degree bounded by . We show that exists for any non-bipartite graph. This verifies for graphs the conjecture of Feder, Hell, and Huang that any that is -complete, is -complete for instances of some maximum degree. Furthermore, we show the same for all projective s, and we get constant upper bounds on the parameter for various infinite classes of graph. For example, we show that for any graph with girth at least 7 in which every edge lies in a -cycle, where is the odd-girth of . [Copyright &y& Elsevier]