Acyclic Edge Coloring of Graphs with Maximum Degree 4

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycle s. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic e dge coloring using k colors and is denoted by $a^{\mathrm{\prime }}(G)$. It was conjectured by Alon, Sudakov and Zaks that for any simple and finite graph $G$, $a^{\mathrm{\prime }}(G)\le \mathrm{\Delta }+2$, where $\Delta =\Delta(G)$denotesthemaximumdegreeof$G$. We prove the conjecture for connected graphs with $\mathrm{\Delta }(G)\le 4$, with the additional restriction that $m\le 2n-1$, where $n$ is the number of vertices and $m$ is the number of edges in $G$. Note that for any graph $G$, $m\le 2n$, when $\mathrm{\Delta }(G)\le 4$. It follows that for any graph $G$ if $\mathrm{\Delta }(G)\le 4$, then $a^{\mathrm{\prime }}(G)\le 7$.