Proper edge coloring with rainbow diamonds

Abstract

Motivated by the B-coloring defined by Gyárfás and Sárközy, we introduce a new edge coloring called \emph{D-coloring}. For a graph $G$, a D-coloring of $G$ is a proper edge coloring such that every diamond subgraph is rainbow. The \emph{D-chromatic index} of $G$, denoted by $\ddot{I}{‡}_D^{\prime }(G)$, is the minimum number of colors needed for a D-coloring of $G$. Denote by $\hat{I}”$ the maximum degree of $G$. We prove that $\ddot{I}{‡}_D^{\prime }(G)\le \frac{9}{16}\hat{I}{”}^2+\frac{1}{2}\hat{I}”$, conjecture that $\ddot{I}{‡}_D^{\prime }(G)\le \frac{1}{2}\hat{I}{”}^2+\frac{1}{2}\hat{I}”$, and verify this conjecture for $\hat{I}”\le 5$.

16 pages, 9 figures, comments are welcome