Article ID Journal Published Year Pages File Type
419859 Discrete Applied Mathematics 2011 9 Pages PDF
Abstract

Given a graph G=(V,E)G=(V,E), a vertex colouring of VV is tt-frugal   if no colour appears more than tt 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 et al. (1997)  [14] studied proper tt-frugal colourings and Yuster (1998) [22] studied acyclic proper 2-frugal colourings. In this paper, we expand and generalise this study.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,