Acyclic improper colouring of graphs with maximum degree 4 |
| |
Authors: | Anna Fiedorowicz Elżbieta Sidorowicz |
| |
Affiliation: | 1. Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Zielona Góra, 65-516, Poland
|
| |
Abstract: | A k-colouring (not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given (hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree 4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) ? 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3. |
| |
Keywords: | acyclic colouring acyclic improper colouring bounded degree graph hereditary property |
本文献已被 CNKI SpringerLink 等数据库收录! |
|