On graph coloring in a class of parallel local algorithms

One of the ways for improving the performance of a distributed algorithm is representation of the coloring strategy into the algorithm which, as known, is efficient in non-distributed algorithms. In this paper we show that application of a certain sequential coloring algorithm heuristics such as the largest-first (SL), the smallest-last (SL) and the saturation largest-first (SLF) for some classes of graphs and for special cases of the vertex coloring in the distributed algorithms give us optimal or near-optimal coloring.