Proper Additive Edge Colorings of Regular Graphs

Abstract

We show that if $G$ is a $d$-regular Vizing-class-1 graph, then the proper additive chromatic index of $G$, denoted $\hat{I}{\cdot }_p^{\prime }(G)$, is equal to its chromatic index. This verifies that a strengthening of the Additive Coloring Conjecture of Czerwiński et al. holds for line graphs of $d$-regular Vizing-class-1 graphs. We show that if $G$ is a $d$-regular Vizing-class-2 graph, $\hat{I}{\cdot }_p^{\prime }(G)\le \frac{(2^{\lceil {\log }_2(d+1)\rceil }{)}^2+2}{3}$, and if $G$ is a $d$-regular Vizing-class-2 graph that admits a proper edge-coloring with a smallest color class of size $r$ and $\text{girth}(G)\ge 6r-5$, then $\hat{I}{\cdot }_p^{\prime }(G)\le 2d$, among other results.

notation errors fixed in the proof of Proposition 16