Modular Neighbor-Distinguishing Edge Colorings of Graphs

Abstract

Let $G$ be a connected graph of order 3 or more and $c:E(G)\to {\mathbb{Z}}_k$ ($k\ge 2$) an edge coloring of $G$ where adjacent edges may be colored the same. The color sum $s(v)$ of a vertex $v$ of $G$ is the sum in ${\mathbb{Z}}_k$ of the colors of the edges incident with $v$. An edge coloring $c$ is a modular neighbor-distinguishing $k$-edge coloring of $G$ if $s(u)\ne s(v)$ in ${\mathbb{Z}}_k$ for all pairs $u,v$ of adjacent vertices of $G$. The modular chromatic index ${\chi }_m^{\prime }(G)$ of $G$ is the minimum $k$ for which $G$ has a modular neighbor-distinguishing $k$-edge coloring. For every graph $G$, it follows that ${\chi }_m^{\prime }(G)\ge \chi (G)$. In particular, it is shown that if $G$ is a graph with $\chi (G)\equiv 2\mathrm{mod}4$ for which every proper $\chi (G)$-coloring of $G$ results in color classes of odd size, then ${\chi }_m^{\prime }(G)>\chi (G)$. The modular chromatic indices of several well-known classes of graphs are determined. It is shown that if $G$ is a connected bipartite graph, then $2\le {\chi }_m^{\prime }(G)\le 3$ and it is determined when each of these two values occurs. There is a discussion on the relationship between ${\chi }_m^{\prime }(G)$ and ${\chi }_m^{\prime }(H)$ when $H$ is a subgraph of $G$.