Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/27299
Título: | Injective edge coloring of graphs |
Autor: | Cardoso, Domingos M. Cerdeira, J. Orestes Dominic, Charles Cruz, J. Pedro |
Palavras-chave: | Injective coloring Injective edge coloring |
Data: | Dez-2019 |
Editora: | Faculty of Sciences and Mathematics, University of Nis |
Resumo: | 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 |
Versão do Editor: | https://www.pmf.ni.ac.rs/filomat |
Aparece nas coleções: | CIDMA - Artigos DMat - Artigos OGTCG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
33-19-27-11820.pdf | 303 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.