Fault tolerant algorithms for orderings and colorings

Summary form only given. A k-forward numbering of a graph is a labeling of the nodes with integers such that each node has less than k neighbors whose labels are equal or larger. We obtain three self-stabilizing (s-s) algorithms for finding a k-forward numbering, provided one exists. One such algorithm also finds the k-height numbering of graph, generalizing s-s algorithms by Bruell et al. and Antonoiu et al. for finding the center of a tree. Another k-forward numbering algorithm runs in polynomial time. There is a strong connection between k-forward numberings and colorings of graphs. We use a k-forward numbering algorithm to obtain an s-s algorithm that is more general than previous coloring algorithms in the literature, and which k-colors any graph having a k-forward numbering. Special cases of the algorithm 6-color planar graphs, thus generalizing an s-s algorithm by Ghosh and Karaata, as well as 2-color trees and 3-color series-parallel graphs. We discuss how our s-s algorithms can be extended to the synchronous model.