### On the injective edge coloring of product graphs and some complexity results

#### Abstract

Three edges e1, e2 and e3 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 e1, e2, e3

are consecutive, then e1 and e3 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)[1]. In this article, injective edge chromatic index of

the resultant graphs obtained 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 J 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.

k-injective edge coloring of a graph G is an edge coloring of G, (not necessarily proper), such that if edges e1, e2, e3

are consecutive, then e1 and e3 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)[1]. In this article, injective edge chromatic index of

the resultant graphs obtained 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 J 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.

### Refbacks

- There are currently no refbacks.