Injective edge-coloring of subcubic graphs.

An injective edge-coloring c of a graph G is an edge-coloring such that if e 1 , e 2 , and e 3 are three consecutive edges in G (they are consecutive if they form a path or a cycle of length three), then e 1 and e 3 receive different colors. The minimum integer k such that, G has an injective edge-coloring with k colors, is called the injective chromatic index of G ( χ inj ′ (G)). This parameter was introduced by Cardoso et al. [Injective coloring of graphs, Filomat 33(19) (2019) 6411–6423, arXiv:1510.02626] motivated by the Packet Radio Network problem. They proved that computing χ inj ′ (G) of a graph G is NP-hard. We give new upper bounds for this parameter and we present the relationships of the injective edge-coloring with other colorings of graphs. We study the injective edge-coloring of some classes of subcubic graphs. We prove that a subcubic bipartite graph has an injective chromatic index bounded by 6. We also prove that if G is a subcubic graph with maximum average degree less than 1 6 7 (respectively, 8 3 ), then G admits an injective edge-coloring with at most 4 (respectively, 6) colors. Moreover, we establish a tight upper bound for subcubic outerplanar graphs. [ABSTRACT FROM AUTHOR]