Injective edge coloring of graphs

Domingos M. Cardoso, J. Orestes Cerdeira, Charles Dominic, J. Pedro Cruz

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Pages (from-to)6411-6423
Number of pages13
JournalFilomat
Volume33
Issue number19
DOIs
Publication statusPublished - 2019

Keywords

  • Injective coloring
  • Injective edge coloring

Fingerprint Dive into the research topics of 'Injective edge coloring of graphs'. Together they form a unique fingerprint.

Cite this