Graph classes with locally irregular chromatic index at most 4 (Q2095566)

A graph is locally irregular if all pairs of adjacent vertices have different degrees. A locally irregular edge colouring is an edge-partition of a graph G into locally irregular subgraphs. There are graphs which do not admit any locally irregular edge colouring (e.g. paths on an odd number of edges), and graphs which admit such a colouring are called decomposable. It is conjectured that each decomposable graph admits a locally irregular edge colouring using at most four colours. The article under review verifies this conjecture for some families of graphs. It is shown: \begin{itemize} \item[1.] All decomposable cactus graphs have a locally irregular edge colouring using at most four colours. \item[2.] All decomposable cactus graphs with no nontrivial cut edges (i.e. edges whose removal leaves two components with at least one edge each) have a locally irregular edge colouring using at most three colours. \item[3.] All decomposable subcubic graphs where each vertex of degree \(3\) lies on a triangle have a locally irregular edge colouring using at most three colours. \item[4.] The graph obtained from a clique on \(n\) vertices after the removal of a cycle on at most \(n-1\) vertices has a locally irregular edge colouring using at most three colours. \end{itemize}