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.