×

Modular neighbor-distinguishing edge colorings of graphs. (English) Zbl 1233.05104

Summary: Let \(G\) be a connected graph of order 3 or more and \(c: E(G) \to {\mathbb{Z}}_k\) (\(k\geq 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) \neq s(v)\) in \({\mathbb{Z}}_k\) for all pairs \(u\), \(v\) of adjacent vertices of \(G\). The modular chromatic index \(\chi_m'(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'(G)\geq\chi(G)\).
In particular, it is shown that if \(G\) is a graph with \(\chi(G)\equiv 2\pmod 4\) for which every proper \(\chi(G)\)-coloring of \(G\) results in color classes of odd size, then \(\chi_m'(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\leq\chi_m'(G)\leq 3\) and it is determined when each of these two values occurs. There is a discussion on the relationship between \(\chi_m'(G)\) and \(\chi_m'(H)\) when \(H\) is a subgraph of \(G\).

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite