Acyclic chromatic indices of fully subdivided graphs
Let G = (V, E) be any finite simple graph. A mapping phi : E -> vertical bar k vertical bar is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. The smallest number k of colours such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by chi(a)'(G). Fiamcik proved that Delta(G) . (Delta(G) - 1) + 1 is an upper bound for the acyclic chromatic index of a graph G and conjectured that chi(a)' (G)  = 3 or G is acyclic. Our proof is constructive and hence yields a polynomial time algorithm. This result is an extension of a result obtained in 1984 by Fiamcik for subdivisions of cubic graphs and improves a recent result presented by Muthu et al. (C) 2012 Elsevier B.V. All rights reserved.
combinatorial problems acyclic edge colouring graph subdivision graph algorithms