Injective edge coloring of graphs

Title

Injective edge coloring of graphs

Creator

Cardoso D.M.; Cerdeira J.O.; Dominic C.; Cruz J.P.

Description

Three edges e1, e2 and e3 in a graph G are consecutive if they form a path (in this order) or a cycle of lengths three. An injective edge coloring of a graph G = (V, E) is a coloring c of the edges of G such that if e1, e2 and e3 are consecutive edges in G, then c(e1) ? c(e3). The injective edge coloring number ?? i (G) is the minimum number of colors permitted in such a coloring. In this paper, exact values of ?? i(G) for several classes of graphs are obtained, upper and lower bounds for ?? i (G) are introduced and it is proven that checking whether ?? i (G) = k is NP-complete. 2019, University of Nis. All rights reserved.

Source

Filomat, Vol-33, No. 19, pp. 6411-6423.

Date

2019-01-01

Publisher

University of Nis

Subject

Injective coloring; Injective edge coloring

Coverage

Cardoso D.M., Center for Research and Development in Mathematics and Applications, Department of Mathematics, Universidade de Aveiro, Aveiro, 3810-193, Portugal; Cerdeira J.O., Department of Mathematics and Center of Mathematics and Applications (CMA), Faculty of Sciences and Technology, New University of Lisbon, Quinta da Torre, Caparica, 2829-516, Portugal; Dominic C., Department of Mathematics, CHRIST(Deemed to be University), Begaluru, 560029, Karnataka, India; Cruz J.P., Center for Research and Development in Mathematics and Applications, Department of Mathematics, Universidade de Aveiro, Aveiro, 3810-193, Portugal

Rights

All Open Access; Gold Open Access; Green Open Access

Relation

ISSN: 3545180

Format

Online

Language

English

Type

Article

Identifier

https://doi.org/10.2298/FIL1919411C

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85078949782&doi=10.2298%2fFIL1919411C&partnerID=40&md5=c5c8ec9e5162e3c3a9dda510ab24c66e