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(G)\), is the smallest number of colors allowing an acyclic edge-coloring of \(G\). Clearly \(\chi'_a(G)\ge \Delta(G)\) for every graph \(G\). Cohen, Havet, and M\"{u}ller conjectured that there exists a constant \(M\) such that every planar graph with \(\Delta(G)\ge M\) has \(\chi'_a(G)=\Delta(G)\). We prove this conjecture.