A Self-Stabilizing (Δ+ 1)- Edge-Coloring Algorithm of Arbitrary Graphs

Given a graph G = (V, E), an edge-coloring of G is a function from the set of edges E to colors {1, 2. .., k} such that any two adjacent edges are assigned different colors. In this paper, we propose a self-stabilizing edge-coloring algorithm in a polynomial number of moves. The protocol assumes the unfair central dæmon and the coloring is a (Δ + 1)-edge-coloring of G, where Δ is the maximum degree in G. To our knowledge, we give the first self-stabilizing edge-coloring algorithm using (Δ + 1) colors of arbitrary graphs.