Injective edge coloring of product graphs and some complexity results


Bhanupriya C Ka, Charles Dominic, Sunitha M Sa




Three edges e 1 , e 2 and e 3 in a graph G are consecutive if they form a cycle of length 3 or a path in this order. A k-injective edge coloring of a graph G is an edge coloring of G, (not necessarily proper), such that if edges e 1 , e 2 , e 3 are consecutive, then e 1 and e 3 receive distinct colors. The minimum k for which G has a k-injective edge coloring is called the injective edge chromatic index, denoted by χ ′ i (G) [4]. In this article, the injective edge chromatic index of the resultant graphs by the operations union, join, Cartesian product and corona product of G and H are determined, where G and H are different classes of graphs. Also for any two arbitrary graphs G and H, bounds for χ ′ i (G + H) and χ ′ i (G H) are obtained. Moreover the injective edge coloring problem restricted to (2, 3, r)-triregular graph, (2, 4, r)-triregular graph and (2, r)-biregular graph, r ≥ 3 are also been demonstrated to be NP-complete.