Displaying similar documents to “Edge and total choosability of near-outerplanar graphs.”

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

Anna Fiedorowicz (2013)

Discussiones Mathematicae Graph Theory

Similarity:

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