Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree
Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 1, p. 91.

Voir la notice de l'article dans European Digital Mathematics Library

A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum 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.
Classification : 05C07, 05C10, 05C15, 05C35
Mots-clés : acyclic colouring, bounded degree graph, maximum average degree 
@article{DMGT_2013__33_1_267614,
     author = {Anna Fiedorowicz},
     title = {Acyclic {6-Colouring} of {Graphs} with {Maximum} {Degree} 5 and {Small} {Maximum} {Average} {Degree}},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {91},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     zbl = {1291.05061},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_1_267614/}
}
TY  - JOUR
AU  - Anna Fiedorowicz
TI  - Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree
JO  - Discussiones Mathematicae Graph Theory
PY  - 2013
SP  - 91
VL  - 33
IS  - 1
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_1_267614/
LA  - en
ID  - DMGT_2013__33_1_267614
ER  - 
%0 Journal Article
%A Anna Fiedorowicz
%T Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree
%J Discussiones Mathematicae Graph Theory
%D 2013
%P 91
%V 33
%N 1
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_1_267614/
%G en
%F DMGT_2013__33_1_267614
Anna Fiedorowicz. Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 1, p. 91. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_1_267614/