The complexity of frugal colouring.

A - of a graph is an assignment of colours to the vertices of , such that each colour appears at most times in the neighbourhood of any vertex. A dichotomy theorem for the complexity of deciding whether a graph has a 1-frugal colouring with colours was found by McCormick and Thomas, and then later extended to restricted graph classes by Kratochvil and Siggers. We generalize the McCormick and Thomas theorem by proving a dichotomy theorem for the complexity of deciding whether a graph has a -frugal colouring with colours, for all pairs of positive integers and . We also generalize bounds of Lih et al. for the number of colours needed in a 1-frugal colouring of a given -minor-free graph with maximum degree to -frugal colourings, for any positive integer .