A Fault-Containing Self-Stabilizing Algorithm for 6-Coloring Planar Graphs

摘要

This paper presents the first fault-containing self-stabilizing algorithm which can 6-color any planar graph. Besides the capability to contain the fault in any single-fault situation, the proposed algorithm also has the capability to stabilize faster in single-fault situations. For single-fault situations, the worst-case stabilization time of the proposed algorithm is O(Δ), whereas the worst-case stabilization times of all the previous self-stabilizing algorithms for 6-coloring planar graphs are Ω(n), where Δ is the maximum node degree, and n is the number of nodes in the system.