Three edges $e_{ 1}, e_{ 2}$ and $e_{ 3}$ in a graph $G$ are consecutive if they form a path (in this order) or a cycle of length three. An injective edge coloring of a graph $G = (V,E)$ is a coloring $c$ of the edges of $G$ such that if $e_{ 1}, e_{ 2}$ and $e_{ 3}$ are consecutive edges in $G$, then $c(e_{ 1})\neq c(e_3)$. The injective edge coloring number $\chi_{ i}^{ '}(G)$ is the minimum number of colors permitted in such a coloring. In this paper, exact values of $\chi_{ i}^{ '}(G)$ for several classes of graphs are obtained, upper and lower bounds for $\chi_{ i}^{ '}(G)$ are introduced and it is proven that checking whether $\chi_{ i}^{ '}(G)= k$ is NP-complete.
Categories: math.CO