A Self-Stabilizing Algorithm for Coloring Planar Graphs

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. Keywords and Phrases: Self-stabilization, distributed algorithm, graph coloring, directed acyclic graph, atomicity. 1 Introduction Graph coloring is a classical problem in graph theory. The primary objective of graph coloring is to assign colors (from a given set) to the nodes of a graph, so that no two neighboring nodes have the same color. Of particular interest is the class of planar graphs, that has received substantial attention so far. A proof for 4-colorability already exists [1], and several algorithms [2] [5] [6] for node coloring are available with no more than five colors...