Acyclic chromatic indices of fully subdivided graphs

Let G=(V,E)G=(V,E) be any finite simple graph. A mapping φ:E→[k]φ:E→[k] 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 χa′(G). Fiamčík proved that Δ(G)⋅(Δ(G)−1)+1Δ(G)⋅(Δ(G)−1)+1 is an upper bound for the acyclic chromatic index of a graph G   and conjectured that χa′(G)⩽Δ(G)+2. In 1991, Alon et al. proved that χa′(G)⩽64Δ(G). This bound was later improved to 16Δ(G)16Δ(G) by Molloy and Reed.In this paper we completely determine the acyclic chromatic index of the class of fully subdivided graphs. Namely, we prove that if we subdivide all edges of a given graph H, then for the obtained graph G   it holds χa′(G)=Δ(G), provided Δ(G)⩾3Δ(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 Fiamčík for subdivisions of cubic graphs and improves a recent result presented by Muthu et al.

► We consider acyclic edge colourings of graphs.
► We determine the acyclic chromatic index of fully subdivided graphs.
► It improves previous results of Fiamčík and Muthu et al.