Back to Search
Start Over
Injective edge-coloring of subcubic graphs.
- Source :
- Discrete Mathematics, Algorithms & Applications; Nov2022, Vol. 14 Issue 8, p1-22, 22p
- Publication Year :
- 2022
-
Abstract
- 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]
- Subjects :
- GRAPH coloring
BIPARTITE graphs
RADIO networks
PLANAR graphs
Subjects
Details
- Language :
- English
- ISSN :
- 17938309
- Volume :
- 14
- Issue :
- 8
- Database :
- Complementary Index
- Journal :
- Discrete Mathematics, Algorithms & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 160454380
- Full Text :
- https://doi.org/10.1142/S1793830922500409