On the complexity of determining the irregular chromatic index of a graph

An undirected simple graph G is locally irregular if adjacent vertices of G have different degrees. Anedge-colouring phi of G is locally irregular if each colour class of phi induces a locally irregular subgraph ofG. The irregular chromatic index chi'(irr)(G) of G is the least number of colours used by a locally irregular edge-colouring ofG(if any). We show that the problem of determining the irregular chromatic index of a graph can be handled in linear time when restricted to trees, but it remains NP-complete in general. (C) 2014 Elsevier B.V. All rights reserved.