D-coloring of planar graphs

Abstract

A proper edge-coloring of a graph $G$ is a D-coloring if every subgraph isomorphic to $K_4-e$ is rainbow. The minimum number of colors in such a coloring is the D-chromatic index ${\chi }_D^{\prime }(G)$. Wang conjectured that every planar graph of maximum degree $\Delta \ge 4$ satisfies ${\chi }_D^{\prime }(G)\le 9$ for $\Delta =4$, ${\chi }_D^{\prime }(G)\le 10$ for $\Delta =5$, and ${\chi }_D^{\prime }(G)\le 2\Delta -1$ for $\Delta \ge 6$. We prove that every planar graph $G$ satisfies \[ χ_D'(G) \leq \begin{cases} 9, & Δ(G) \leq 4, \\ 10, & Δ(G) = 5, \\ 2Δ(G) - 1, & Δ(G) \geq 33. \end{cases} \] Each bound is best possible in its stated range. Consequently, Wang's conjecture remains open only for $6\le \Delta \le 32$.