The Injective Chromatic Index of a Claw-Free Subcubic Graph is at Most 6

Abstract:

      A coloring of edges of a graph $G$ is injective if for any two distinct edges $e_1$ and $e_2$, the coloring of $e_1$ and $e_2$ are distinct if they are at distance $2$ in $G$ or in a common $3$-cycle. The injective chromatic index of $G$ is the minimum number of colors needed for an injective edge coloring of $G$. It was conjectured that the injective chromatic index of any subcubic graph is at most $6$. In this paper, we partially confirm this conjecture by showing that the injective chromatic index of any claw-free subcubic graph is less than or equal to $6$. The bound $6$ is tight and our proof implies a linear-time algorithm for finding an injective edge coloring using at most $6$ colors for such graphs.