Injective edge coloring of graphs
subject: Injective coloring; Injective edge coloring
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.
creator: Cardoso D.M.; Cerdeira J.O.; Dominic C.; Cruz J.P.
source: Filomat, Vol-33, No. 19, pp. 6411-6423.
publisher: University of Nis
date: 2019-01-01
rights: All Open Access; Gold Open Access; Green Open Access
relation: ISSN: 3545180
format: Online
language: English
type: Article
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