An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
Eshrat Arjomandi · INFOR Information Systems and Operational Research · 1982
The edge colouring problem has received considerable attention from mathematicians andcomputer scientists. The edges of a simple graph G can be coloured with Δ or Δ + 1 colours, where Δ is the maximum degree in G. Holyer has recently shown that A-edgecolourability is NP-complete. In this paper we present a edge colouring algorithm for general graphs which uses at most Δ + 1 colours.