Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431268 | Journal of Discrete Algorithms | 2015 | 15 Pages |
Abstract
An undirected simple graph G is locally irregular if adjacent vertices of G have different degrees. An edge-colouring ϕ of G is locally irregular if each colour class of ϕ induces a locally irregular subgraph of G . The irregular chromatic index χirr′(G) of G is the least number of colours used by a locally irregular edge-colouring of G (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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Olivier Baudon, Julien Bensmail, Éric Sopena,