A Note on the Locally Irregular Edge Colorings of Cacti
Jelena Sedlar, Riste Škrekovski · Discrete Mathematics Letters · 2022
A graph is locally irregular if the degrees of the end-vertices of every edge are distinct.An edge coloring of a graph G is locally irregular if every color induces a locally irregular subgraph of G.A colorable graph G is any graph which admits a locally irregular edge coloring.The locally irregular chromatic index χ irr (G) of a colorable graph G is the smallest number of colors required by a locally irregular edge coloring of G.The Local Irregularity Conjecture claims that all colorable graphs require at most 3 colors for a locally irregular edge coloring.Recently, it has been observed that the conjecture does not hold for the bow-tie graph B, since B is colorable and requires at least 4 colors for a locally irregular edge coloring.Since B is a cactus graph and all non-colorable graphs are also cacti, this seems to be a relevant class of graphs for the Local Irregularity Conjecture.In this paper, it is proved that χ irr (G) ≤ 4 for all colorable cactus graphs.