A self-stabilizing algorithm for coloring planar graphs.

S Ghosh and MH Karaata, Distributed Computing 7, 1993, pp. 55-59:

Postscript Document and DVI file.

Abstract

This paper describes an algorithm for coloring the nodes of a planar graph with no more than six colors using a self-stabilizing approach. The first part illustrates the coloring algorithm on a directed acyclic version of the given planar graph. The second part describes a self-stabilizing algorithm for generating the directed acyclic version of the planar graph, and combines the two algorithms into one.