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 co...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 acyclie k-eolourings such that each colour class induces a graph with a given （hereditary） property. In particular, we consider aeyclic k-eolourings 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 acyelic 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 A（G） ≤ 4 can be acyelically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.展开更多
基金supported by the Minister of Science and Higher Education of Poland(Grant No.JP2010009070)
文摘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 acyclie k-eolourings such that each colour class induces a graph with a given （hereditary） property. In particular, we consider aeyclic k-eolourings 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 acyelic 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 A（G） ≤ 4 can be acyelically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.
