Injective edge-coloring of sparse graphs
B Ferdjallah, S Kerdjoudj, A Raspaud�- arXiv preprint arXiv:1907.09838, 2019 - arxiv.org
B Ferdjallah, S Kerdjoudj, A Raspaud
arXiv preprint arXiv:1907.09838, 2019•arxiv.orgAn 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 $($\chi'_ {\textrm {inj}}(G) $). This parameter was
introduced by Cardoso et\textit {al.}\cite {CCCD} motivated by the Packet Radio Network�…
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 $($\chi'_ {\textrm {inj}}(G) $). This parameter was
introduced by Cardoso et\textit {al.}\cite {CCCD} motivated by the Packet Radio Network�…
An injective edge-coloring of a graph is an edge-coloring such that if , , and are three consecutive edges in (they are consecutive if they form a path or a cycle of length three), then and receive different colors. The minimum integer such that, has an injective edge-coloring with colors, is called the injective chromatic index of (). This parameter was introduced by Cardoso et \textit{al.} \cite{CCCD} motivated by the Packet Radio Network problem. They proved that computing of a graph 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 . We also prove that if is a subcubic graph with maximum average degree less than (resp. , ), then admits an injective edge-coloring with at most 4 (resp. , ) colors. Moreover, we establish a tight upper bound for subcubic outerplanar graphs.
arxiv.org