Acyclic edge colorings of graphs (Q2746208)

A regular colouring of the edges of a finite simple graph \(G\) is acyclic if there is no 2-coloured cycle in \(G\) (the union of any two colour classes induces of a forest). The acyclic edge chromatic number \(a'(G)\) of \(G\) is the least number of colours in an acyclic edge colouring of \(G\). It is conjectured that \(a'(G)\leq\Delta(G)+ 2\) for all graphs \(G\), where \(\Delta(G)\) is the maximum vertex degree of \(G\). The authors show (among other things) that this conjecture holds for almost all \(\Delta\)-regular graphs. We can embed every graph with \(\Delta\) into a \(\Delta\)-regular graph. It follows that the conjecture is true for almost all graphs.NEWLINENEWLINENEWLINEThe same conjecture was made and verified for \(\Delta= 3\) in \textit{J. Fiamčík} [Acyclic chromatic index of a graph (Russian), Math. Slovaca 28, 139-145 (1978; Zbl 0388.05015)].