06059708

j

06059708 Fiedorowicz, Anna Ha{\l}uszczak, Mariusz Acyclic chromatic indices of fully subdivided graphs. Inf. Process. Lett. 112, No. 13, 557-561 (2012). 2012 Elsevier Sciences Publishers (North-Holland), Amsterdam EN combinatorial problems acyclic edge colouring graph subdivision Zbl 0735.05036

doi:10.1016/j.ipl.2012.04.004

Summary: Let $G=(V,E)$ be any finite simple graph. A mapping $\varphi :E\to [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 $X'_a(G)$. Fiam\v{c}{\'\i}k proved that $\Delta (G)\cdot (\Delta (G) - 1)+1$ is an upper bound for the acyclic chromatic index of a graph $G$ and conjectured that $X'_a(G) \leq \Delta (G)+2$. In [``Acyclic coloring of graphs,'' Random Struct. Algorithms 2, No. 3, 277--288 (1991; Zbl 0735.05036)], {\it N. Alon}, {\it C. McDiarmid} and {\it B. Reed} proved that $X'_a(G)\leq 64 \Delta (G)$. This bound was later improved to $16\Delta (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 $X'_a (G)$, provided $\Delta(G) \geq3$ 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\v{c}{\'\i}k [{\it J. Fiam\v{c}{\'\i}k}, ``Acyclic chromatic index of a subdivided graph,'' Arch. Math., Brno 20, 69--82 (1984; Zbl 0554.05027)] for subdivisions of cubic graphs and improves a recent result presented by Muthu et al.