A stronger upper bound on the D-chromatic index

Abstract

For a graph $G$, a proper edge coloring of $G$ is called a D-coloring if every diamond subgraph of $G$ is rainbow. Let ${\chi }_D^{\prime }(G)$ be the D-chromatic index of $G$, which is the smallest integer $k$ such that $G$ admits a D-coloring with $k$ colors. Let $\Delta$ be the maximum degree of $G$. The only known Brooks-type upper bound on ${\chi }_D^{\prime }(G)$ is $\frac{9}{16}{\Delta }^2+\frac{1}{2}\Delta$, given by a greedy coloring. In this paper, using a probabilistic method, we obtain the first improvement upon this upper bound by proving that ${\chi }_D^{\prime }(G)\le (1-c)\frac{9}{16}{\Delta }^2$ for some $c>0$ and sufficiently large $\Delta$.