Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces

A sequential graph coloring algorithm and a strict distributed (broadcasting type) algorithm , and an analysis of their performance in scales of random graph spaces is presented. For a space of graphs with n vertices and a mean degree d(n), the number of colors produced is almost surely bounded by about d(n)/logd(n), which is almost surely not more than twice the chromatic number, and the distributed algorithm terminates in O(Max(d(n),logn)) steps.