Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419859 | Discrete Applied Mathematics | 2011 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ross J. Kang, Tobias Müller,