Acyclic edge-coloring of planar graphs: $\Delta$ colors suffice when $\Delta$ is large

Abstract

An \emph{acyclic edge-coloring} of a graph $G$ is a proper edge-coloring of $G$ such that the subgraph induced by any two color classes is acyclic. The \emph{acyclic chromatic index}, ${\chi }_a^{\prime }(G)$, is the smallest number of colors allowing an acyclic edge-coloring of $G$. Clearly ${\chi }_a^{\prime }(G)\ge \Delta (G)$ for every graph $G$. Cohen, Havet, and Müller conjectured that there exists a constant $M$ such that every planar graph with $\Delta (G)\ge M$ has ${\chi }_a^{\prime }(G)=\Delta (G)$. We prove this conjecture.

arXiv comment15 pages, 8 figures; minor revisions to incorporate reviewer feedback; to appear in SIAM J. Discrete Math