×

zbMATH — the first resource for mathematics

On modular chromatic indexes of graphs. (English) Zbl 1251.05057
Summary: For a connected graph \(G\) of order 3 or more and an edge coloring \(c: E(G)\to\mathbb{Z}_k\) (\(k\geq 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)\neq s(v)\) in \(\mathbb{Z}_k\) for all pairs \(u\), \(v\) of adjacent vertices in \(G\).
The modular chromatic index \(\chi_m'(G)\) of \(G\) is the minimum \(k\) for which \(G\) has a modular \(k\)-edge coloring. It is shown that \(\chi(G)\leq\chi_m'(G)\leq\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'(G)= \chi(G)+ 1\) if and only if \(\chi(G) \equiv 2 \pmod 4\) and every proper \(\chi(G)\)-coloring of \(G\) results in color classes of odd size.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite