Acyclic edge colouring: Bounds and algorithms[HBNI Th3]

Abstract

An acyclic edge colouring of a graph is an assignment of colours to its edges in such a way that incident edges get distinct colours, and the edges of any cycle use atleast three distinct colours. The latter condition is equivalent to the requirement that the subgraph induced by any pair of colour classes (set of edges receiving the same colour) is a forest. The minimum number of colours sufficient to acyclically colour the edges of a graph G, is called its acyclic chromatic index. This thesis studies the notion 'the acyclic edge colouring of graphs', in the context of two different aims, i) to get tight estimates on the minimum number of colours sufficient to achieve such colourings for any graph; ii) to actually produce such colourings using as few colours as possible. The acyclic colouring problem can be viewed from a combinatorial perspective and also from an algorithmic perspective. No good estimates on (Alpha)'(G) have been obtained for even highly structured classes like the complete graphs, or restricted families like bipartite graphs. From the algorithmic point of view it is NP-Hard to determine Alpha'(G) in general and even when restricted to subcubic, 2-degenerate graphs. Its close relationship to standard vertex colourings indicates that it could be useful in modelling and solving problems involving conflict free scheduling of activities. The acyclic edge colouring problem is also closely related to star and oriented colourings of line graphs which have applications in protocols for mobile communication.