Acyclic edge colouring: Bounds and algorithms[HBNI Th 3]

DSpace/Manakin Repository

Acyclic edge colouring: Bounds and algorithms[HBNI Th 3]

Show simple item record Rahul Muthu 2009-09-15T07:08:32Z 2009-09-15T07:08:32Z 2009-09-15T07:08:32Z 2008
dc.description.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. en_US
dc.subject Graph Colouring en_US
dc.subject Algorithm en_US
dc.subject Combinatorics en_US
dc.title Acyclic edge colouring: Bounds and algorithms[HBNI Th 3] en_US Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Subramanian, C. R.
dc.description.pages x; 72p. en_US
dc.type.mainsub Computer Science en_US

Files in this item

Files Size Format View
rahulmuthu.pdf 644.2Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account