Jelena Sedlar: Remarks on the local irregularity conjecture

A locally irregular graph is a graph in which the end-vertices of every edge have distinct degrees. A locally irregular edge coloring of a graph G is any edge coloring of G such that each of the colors induces a locally irregular subgraph of G. A graph G is colorable if it admits a locally irregular edge coloring. The locally irregular chromatic index of a colorable graph G is the smallest number of colors used by a locally irregular edge coloring of G. The Local Irregularity Conjecture claims that all graphs, except odd length path, odd length cycle and a certain class of cacti, are colorable by 3 colors. It was already established that the conjecture holds for trees and all trees for which the locally irregular chromatic index equals 3 are characterized. We take this consideration a step further to the unicyclic graphs, since they are obtained from trees by inserting a single edge. First we establish several auxiliary results for trees and then we show that the Local Irregularity Conjecture holds for unicyclic graphs. Finally, we give some remarks on the locally irregular chromatic index of cacti.

Joint work with Riste Škrekovski.