On Modular Chromatic Indexes of Graphs

Abstract

For a connected graph $G$ of order $3$ or more and an edge coloring $c:E(G)\to {\mathbb{Z}}_k$ ($k\ge 2$) 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$. The edge coloring $c$ is a modular $k$-edge coloring of $G$ if $s(u)\ne s(v)$ in ${\mathbb{Z}}_k$ for all pairs $u,v$ of adjacent vertices in $G$. The modular chromatic index ${\chi }_m^{\prime }(G)$ of $G$ is the minimum $k$ for which $G$ has a modular $k$-edge coloring. It is shown that $\chi (G)\le {\chi }_m^{\prime }(G)\le \chi (G)+1$ for every connected graph $G$ of order at least 3, where $\chi (G)$ is the chromatic number of $G$. Furthermore, it is shown that ${\chi }_m^{\prime }(G)=\chi (G)+1$ if and only if $\chi (G)\equiv 2(\mathrm{mod}4)$ and every proper $\chi (G)$-coloring of $G$ results in color classes of odd size.