Run-Ze Wang

A stronger upper bound on the D-chromatic index

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(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(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(G) \le (1-c)\frac{9}{16}\Delta^2$ for some $c>0$ and sufficiently large $\Delta$.