Injective Edge Chromatic Index of a Graph

Abstract

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)\ne c(e_3)$. The injective edge coloring number ${\chi }_i^{{}^{\prime }}(G)$ is the minimum number of colors permitted in such a coloring. In this paper, exact values of ${\chi }_i^{{}^{\prime }}(G)$ for several classes of graphs are obtained, upper and lower bounds for ${\chi }_i^{{}^{\prime }}(G)$ are introduced and it is proven that checking whether ${\chi }_i^{{}^{\prime }}(G)=k$ is NP-complete.

Cited by in corpus (2)

• Injective edge-coloring of sparse graphs
• Injective edge-coloring of graphs with given maximum degree