Discussiones Mathematicae Graph Theory 33(1) (2013)
91-99

doi: 10.7151/dmgt.1665

*Dedicated to Mieczysław Borowiecki on the occasion of his 70th birthday*

Anna Fiedorowicz
Faculty of Mathematics, Computer Science and Econometrics |

Acyclic colourings were introduced by Grünbaum in 1973, and since then have been widely studied. In particular, the problem of acyclic colourings of graphs with bounded maximum degree has been investigated. In 2011, Kostochka and Stocker showed that any graph with maximum degree 5 can be acyclically coloured with at most 7 colours. The question, whether this bound is achieved, remains open. In this note we prove that any graph with maximum degree 5 and maximum average degree at most 4 admits an acyclic 6-colouring. We also provide examples of graphs with these properties.

**Keywords:** acyclic colouring, bounded degree graph, maximum average degree

**2010 Mathematics Subject Classification:** 05C15.

[1] | O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211--236, doi: 10.1016/0012-365X(79)90077-3 . |

[2] | O.V. Borodin, A.V. Kostochka and D.R. Woodall, Acyclic colorings of planar graphs with large girth, J. Lond. Math. Soc. 60 (1999) 344--352, doi: 10.1112/S0024610799007942. |

[3] | M.I. Burstein, Every , Soobšč. Akad. Gruzin. SSR 4-valent graph has an acyclic 5-coloring 93 (1979) 21--24 (in Russian). |

[4] | G. Fertin and A. Raspaud, Acyclic coloring of graphs of maximum degree five: Nine colors are enough, Inform. Process. Lett. 105 (2008) 65--72, doi: 10.1016/j.ipl.2007.08.022. |

[5] | B. Grünbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390--408, doi: 10.1007/BF02764716. |

[6] | A.V. Kostochka, Upper bounds of chromatic functions of graphs, Ph.D. Thesis, Novosibirsk, 1978 (in Russian). |

[7] | A.V. Kostochka and C. Stocker, Graphs with maximum degree , Ars Math. Contemp. 5 are acyclically 7-colorable 4 (2011) 153--164. |

[8] | S. Skulrattanakulchai, Acyclic colorings of subcubic graphs, Inform. Process. Lett. 92 (2004) 161--167, doi: 10.1016/j.ipl.2004.08.002. |

[9] | D. West, Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, 2001). |

Received 14 July 2012

Revised 14 November 2012

Accepted 15 November 2012