2019/07/23 by Baya Ferdjallah, Ferdjallah, Baya, Samia Kerdjoudj +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1907.09838
openalex publication_date 2019/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An injective edge-coloring c of a graph G is an edge-coloring such that if e1, e2, and e3 are three consecutive edges in G (they are consecutive if they form a path or a cycle of length three), then e1 and e3 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 (χ'_\textrminj(G)). This parameter was introduced by Cardoso et al. \citeCCCD motivated by the Packet Radio Network problem. They proved that computing χ'_\textrminj(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. The obtained general bound gives 8 for the injective chromatic index of a subcubic graph. If the graph is subcubic bipartite we improve this last bound. 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 (7)/(3) (resp. (8)/(3) , 3), then G admits an injective edge-coloring with at most 4 (resp. 6, 7) colors. Moreover, we establish a tight upper bound for subcubic outerplanar graphs.