Modular edge colorings of Mycielskian graphs

Document Type : Research Paper


Annamalai University


Let $G$ be a connected graph of order $3$ or more and $c:E(G)\rightarrow\mathbb{Z}_k$‎ ‎($k\ge 2$) a $k$-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.$ The $k$-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 of $G.$ The modular chromatic index $\chi'_m(G)$ of $G$ is the minimum $k$ for which $G$ has a modular $k$-edge coloring‎. ‎The Mycielskian of $G\,=\,(V,E)$ is the graph $\mathscr{M}(G)$ with vertex set $V\cup V'\cup\{u\},$ where $V'=\{v':v\in V\},$ and edge set $E\cup\{xy':xy\in E\}\cup\{v'u:v'\in V'\}.$ It is shown that $\chi'_m(\mathscr{M}(G))\,=\,\chi(\mathscr{M}(G))$ for some bipartite graphs‎, ‎cycles and complete graphs‎.


Main Subjects

R‎. ‎Balakrishnan and K‎. ‎Ranganathan (2012). A textbook of graph theory. ‎Second edition‎, ‎Universitext‎, ‎Springer‎, ‎New York. R‎. ‎Jones‎, ‎K‎. ‎Kolasinski‎, ‎F‎. ‎Okamoto and P‎. ‎Zhang (2011). ‎Modular Neighbor-Distinguishing Edge Colorings of Graphs. J‎. ‎Combin‎. ‎Math‎. ‎Combin‎. ‎Comput.. 76, 159-175
Volume 4, Issue 3 - Serial Number 3
September 2015
Pages 53-61
  • Receive Date: 19 September 2013
  • Revise Date: 16 November 2014
  • Accept Date: 16 November 2014
  • Published Online: 01 September 2015