Acyclic Edge-Coloring of Planar Graphs: $\Delta$ Colors Suffice When $\Delta$ is Large
Daniel W. Cranston · SIAM Journal on Discrete Mathematics · 2019
An 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 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ü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.