Acyclic Edge coloring of Planar Graphs

Abstract

An $acyclic$ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The \emph{acyclic chromatic index} of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by $a^{\prime }(G)$. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that $a^{\prime }(G)\le \Delta +2$, where $\Delta =\Delta (G)$ denotes the maximum degree of the graph. We prove that if $G$ is a planar graph with maximum degree $\Delta$, then $a^{\prime }(G)\le \Delta +12$.

10 pages. 0 figures

References in corpus (1)

• Acyclic Edge colorings of 2-degenerate graphs