Injective edge-coloring of subcubic graphs

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

(

c h i'_{e x t r m i n j} (G)

). This parameter was introduced by Cardoso et extit{al.} cite{CCCD} motivated by the Packet Radio Network problem. They proved that computing

c h i'_{e x t r m i n j} (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

f r a c 73

(resp.

f r a c 83

,

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.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Injective edge-coloring of subcubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115745)