Given a graph G = (V,E), a proper vertex colouring of V is t-frugal if no colour appears more than t times in any neighbourhood and is acyclic if each of the bipartite graphs consisting of the edges between any two colour classes is acyclic. For graphs of bounded maximum degree, Hind, Molloy and Reed [14] studied proper t-frugal colourings and Yuster [19] studied acyclic proper 2-frugal colourings. In this paper, we expand and generalise this study. In particular, we consider vertex colourings that are not necessarily proper, and in this case, we find qualitative connections with colourings that are t-improper — colourings in which the colour classes induce subgraphs of maximum degree at most t — for choices of t near to d.
['Ross J. Kang', 'Tobias Muller']
Acyclic and frugal colourings of graphs