Please use this identifier to cite or link to this item:
Title: Injective edge coloring of graphs
Author: Cardoso, Domingos M.
Cerdeira, J. Orestes
Dominic, Charles
Cruz, J. Pedro
Keywords: Injective coloring
Injective 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
DOI: 10.2298/FIL1919411C
ISSN: 0354-5180
Publisher Version:
Appears in Collections:CIDMA - Artigos
DMat - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
33-19-27-11820.pdf303 kBAdobe PDFView/Open

Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.