Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree

Anna Fiedorowicz

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 91-99
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Anna Fiedorowicz. "Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree." Discussiones Mathematicae Graph Theory 33.1 (2013): 91-99. <http://eudml.org/doc/267614>.

@article{AnnaFiedorowicz2013,
abstract = {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.},
author = {Anna Fiedorowicz},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {acyclic colouring; bounded degree graph; maximum average degree},
language = {eng},
number = {1},
pages = {91-99},
title = {Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree},
url = {http://eudml.org/doc/267614},
volume = {33},
year = {2013},
}

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
VL - 33
IS - 1
SP - 91
EP - 99
AB - 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.
LA - eng
KW - acyclic colouring; bounded degree graph; maximum average degree
UR - http://eudml.org/doc/267614
ER -

References

top
  1. [1] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236. doi:10.1016/0012-365X(79)90077-3[Crossref][WoS] 
  2. [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[Crossref] Zbl0940.05032
  3. [3] M.I. Burstein, Every 4-valent graph has an acyclic 5-coloring, Soobˇsˇc. Akad. Gruzin. SSR 93 (1979) 21-24 (in Russian). Zbl0397.05023
  4. [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[Crossref][WoS] Zbl1183.05027
  5. [5] B. Grünbaum, Acyclic coloring of planar graphs, Israel J. Math. 14 (1973) 390-408. doi:10.1007/BF02764716[Crossref] Zbl0265.05103
  6. [6] A.V. Kostochka, Upper bounds of chromatic functions of graphs, Ph.D. Thesis, Novosibirsk, 1978 (in Russian). 
  7. [7] A.V. Kostochka and C. Stocker, Graphs with maximum degree 5 are acyclically 7- colorable, Ars Math. Contemp. 4 (2011) 153-164. Zbl1236.05083
  8. [8] S. Skulrattanakulchai, Acyclic colorings of subcubic graphs, Inform. Process. Lett. 92 (2004) 161-167. doi:10.1016/j.ipl.2004.08.002[Crossref] Zbl1169.05325
  9. [9] D. West, Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.