Modular edge colorings of Mycielskian graphs

Abstract

Let G be a connected graph of order 3 or more and c:E(G)→Z k ‎ ‎(k≥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 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)≠s(v) in Z k for all pairs u, v of adjacent vertices of G. The modular chromatic index χ ′ 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 M(G) with vertex set V∪V ′ ∪{u}, where V ′ ={v ′ :v∈V}, and edge set E∪{xy ′ :xy∈E}∪{v ′ u:v ′ ∈V ′ }. It is shown that χ ′ m (M(G))=χ(M(G)) for some bipartite graphs‎, ‎cycles and complete graphs‎.

Keywords

• modular edge coloring
• modular chromatic index
• Mycielskian of a graph