Acyclic Edge Colouring . . .

An acyclic edge colouring of a graph is a proper edge colouring such that there are no bichromatic cycles. The acyclicchromatic index of a graph is the minimum number k such that there is an acyclic edge colouring using k colours and it isdenoted by a0(G). A graph is called 2-degenerate if each of its subgraphs has a vertex of degree at most 2. The class of 2-degenerate graphs contains important special classes such as series-parallel graphs, partial 2-trees and outerplanar graphs.It was conjectured by Alon, Sudakov and Zaks that a0(G) < = \Delta + 2, where \Delta = \Delta (G) denotes the maximum degree ofthe graph. We prove the conjecture for 2-degenerate graphs, and improve the bound to \Delta + 1 for series-parallel graphs.We also prove that this improved bound holds for the class of partial 2-trees. These latter results actually give best possible upper bounds. All these bounds are proved constructively, leading to effecient algorithms to produce colourings with thestated number of colours