Edge-partitions of graphs and their neighbor-distinguishing index

A proper edge coloring is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The minimum number of colors needed for a neighbor-distinguishing edge coloring is the neighbor-distinguishing index, denoted by ${\chi }_a^{\prime }\left(G\right)$. A graph is normal if it contains no isolated edges. Let $G$ be a normal graph, and let $\Delta \left(G\right)$ and ${\chi }^{\prime }\left(G\right)$ denote the maximum degree and the chromatic index of $G$, respectively. We modify the previously known techniques of edge-partitioning to prove that ${\chi }_a^{\prime }\left(G\right)\le 2{\chi }^{\prime }\left(G\right)$, which implies that ${\chi }_a^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$. This improves the result in Wang et al. (2015), which states that ${\chi }_a^{\prime }\left(G\right)\le \frac{5}{2}\Delta \left(G\right)$ for any normal graph. We also prove that ${\chi }_a^{\prime }\left(G\right)\le 2\Delta \left(G\right)$ when $\Delta \left(G\right)=2^k$, $k$ is an integer with $k\ge 2$.