Abstract
For a graph G = (V, E), a vertex coloring (or, simply, a coloring) of G is a function C : V (G) -> {1, 2, ..., k} (using the non-negative integers {1, 2, ..., k} as colors). We say that a coloring of a graph G is injective if for every vertex v is an element of V (G), all the neighbors of v are assigned with distinct colors. The injective chromatic number chi(i)(G) of a graph G is the least k such that there is an injective k-coloring [6]. In this paper, we study a natural variation of the injective coloring problem: coloring the edges of a graph under the same constraints (alternatively, to investigate the injective chromatic number of line graphs), we define the k-injective edge coloring of a graph G as a mapping C : E(G) -> {1, 2, ..., k}, such that for every edge e is an element of E(G), all the neighbors edges of e are assigned with distinct colors. The injective chromatic index chi'(in)(G) of G is the least positive integer k such that G has k-injective edge coloring, exact values of the injective chromatic index of different families of graphs are obtained, some related results and bounds are established. Finally, we define the injective clique number omega(in) and state a conjecture, that, for any graph G, omega(in) <= chi'(in)(G) <= omega(in) + 2.