首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Acyclic improper colouring of graphs with maximum degree 4
Authors:Anna Fiedorowicz  Elżbieta Sidorowicz
Institution: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号