Chennai Mathematical Institute


Acyclic Edge Colouring - A Survey
Dr N Narayanan
Institute of Mathematical Sciences, Chennai.


A proper edge colouring is acyclic, if the union of any 2 colour clases is a forest. Minimum number of colour required for such a colouring is the acyclic chromatic index $a'(G)$. The problem is proposed by Gr\:unbaum in '73. A linear bound of $16d$ is known for all graphs where $d$ is the maximum degree. It is conjectured that $d+2$ colours will suffice.

Our main results include,

1. If $G$ is of girth at most 220, 6d will suffice. 2. If $G$ is an $n$-dimensional hypecube, hypergrid(mesh) or torus, we show that d or d+1 colours are optimal and colouring can be obtained in linear time. 3. If $G$ is an outerplanar graph, d+1 colours are enough. 4. If $G$ is 2-degenerate, then d+2 colours are enough. Further, if $G$ is a partial 2-tree, then d+1 is optimal. 5. Latest results on planar graphs and 2-fold graphs (

I will give a survey of the results with brief descriptions of the methods used so far including the 16d as well as d+2 results.

Search WWW Search