Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/27299
 Title: Injective edge coloring of graphs Author: Cardoso, Domingos M.Cerdeira, J. OrestesDominic, CharlesCruz, J. Pedro Keywords: Injective coloringInjective edge coloring Issue Date: Dec-2019 Publisher: Faculty of Sciences and Mathematics, University of Nis Abstract: Three edges $e_{1}, e_{2}$ and $e_{3}$ 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 $e_{1}, e_{2}$ and $e_{3}$ are consecutive edges in $G$, then $c(e_{1})\neq c(e_3)$. The injective edge coloring number $\chi_{i}^{'}(G)$ is the minimum number of colors permitted in such a coloring. In this paper, exact values of $\chi_{i}^{'}(G)$ for several classes of graphs are obtained, upper and lower bounds for $\chi_{i}^{'}(G)$ are introduced and it is proven that checking whether $\chi_{i}^{'}(G)= k$ is NP-complete. Peer review: yes URI: http://hdl.handle.net/10773/27299 DOI: 10.2298/FIL1919411C ISSN: 0354-5180 Publisher Version: https://www.pmf.ni.ac.rs/filomat Appears in Collections: CIDMA - ArtigosDMat - ArtigosOGTCG - Artigos

Files in This Item:
File Description SizeFormat