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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Addario-Berry L, Kang R J, Műller T. Acyclic dominating partitions. J Graph Theory, 2010, 64: 292–311
Alon N, Mohar B, Sanders D P. On acyclic colorings of graphs on surfaces. Israel J Math, 1996, 94: 273–283
Boiron P, Sopena E, Vignal L. Acyclic improper colorings of graphs. J Graph Theory, 1999, 32: 97–107
Boiron P, Sopena E, Vignal L. Acyclic improper colourings of graphs with bounded degree. DIMACS Ser Discrete Math Theoret Comput Sci, 1999, 49: 1–9
Borodin O V. On acyclic colorings of planar graphs. Discrete Math, 1979, 25: 211–236
Borodin O V, Kostochka A V, Woodall D R. Acyclic colorings of planar graphs with large girth. J Lond Math Soc, 1999, 60: 344–352
Borodin O V, Kostochka A V, Raspaud A, et al. Acyclic colouring of 1-planar graphs. Discrete Appl Math, 2001, 114: 29–41
Borowiecki M, Broere I, Frick M, et al. A survey of hereditary properties of graphs. Discuss Math Graph Theory, 1997, 17: 5–50
Borowiecki M, Fiedorowicz A, Jesse-Józefczyk K, et al. Acyclic colourings of graphs with bounded degree. Discrete Math Theor Comput Sci, 2010, 12: 59–74
Borowiecki M, Jesse-Józefczyk K, Sidorowicz E. The complexity of some acyclic improper colouring. Discrete Math, 2011, 311: 732–737
Burstein M I. Every 4-valent graph has an acyclic 5-coloring (in Russian). Soobšč Akad Gruzin SSR, 1979, 93: 21–24
Coleman T F, Cai J. The cyclic coloring problem and estimation of sparse Hessian matrices. SIAM J Algebraic Discrete Methods, 1986, 7: 221–235
Coleman T F, Moré J J. Estimation of sparse Hessian matrices and graph coloring problems. Math Program, 1984, 28: 243–270
Gebremedhin A H, Manne F, Pothen A. What color is your Jacobian? Graph coloring for computing derivatives. SIAM Rev, 2005, 47: 629–705
Gebremedhin A H, Pothen A, Walther A, et al. Efficient computation of sparse Hessians using coloring and automatic differentiation. INFORMS J Comput, 2009, 21: 209–223
Grűnbaum B. Acyclic coloring of planar graphs. Israel J Math, 1973, 14: 390–412
Hocquard H. Graphs with maximum degree 6 are acyclically 11-colorable. Inform Process Lett, 2011, 111: 748–753
Kostochka A V. Upper bounds of chromatic functions of graphs (in Russian). PhD Thesis. Novosibirsk: Insitute of Mathematics, 1978
Kostochka A V, Stocker C. Graphs with maximum degree 5 are acyclically 7-colorable. Ars Math Contemp, 2011, 4: 153–164
Lovász L. On decomposition of graphs. Studia Sci Math Hungar, 1966, 1: 237–238
Skulrattanakulchai S. Acyclic colorings of subcubic graphs. Inform Process Lett, 2004, 92: 161–167
West D. Introduction to Graph Theory, 2nd ed. Upper Saddle River: Prentice Hall, 2001
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fiedorowicz, A., Sidorowicz, E. Acyclic improper colouring of graphs with maximum degree 4. Sci. China Math. 57, 2485–2494 (2014). https://doi.org/10.1007/s11425-014-4828-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-014-4828-9