Back to Search Start Over

Injective edge-coloring of graphs with given maximum degree

Authors :
Kostochka, Alexandr
Raspaud, André
Xu, Jingwei
Publication Year :
2020

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$, $\chi'_{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.<br />Comment: 14 pages

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2010.00429
Document Type :
Working Paper