Injective edge-coloring of graphs with given maximum degree. (August 2021)

• Record Type: Journal Article
• Authors: Kostochka, Alexandr; Raspaud, André; Xu, Jingwei
• Is Part Of: European journal of combinatorics. Volume 96(2021)
• Publication Date: 2021-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103355
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: A coloring of edges of a graph G is injective if for any two distinct edges e 1 and e 2, the colors of e 1 and e 2 are distinct if they are at distance 1 in G or in a common triangle. Naturally, the injective chromatic index of G, χ inj ′ ( G ), is the minimum number of colors needed for an injective edge-coloring of G . We study how large can be the injective chromatic index of G in terms of maximum degree of G when we have restrictions on girth and/or chromatic number of G . We also compare our bounds with analogous bounds on the strong chromatic index.