PARALLEL AND ONLINE GRAPH-COLORING

We discover a surprising connection between graph coloring in two orth ogonal paradigms: parallel and on-line computing. We present a randomi zed on-line coloring algorithm with a performance ratio of O(n/log n), an improvement of root log n factor over the previous best known algo rithm of Vishwanathan. Also, from the same principles, we construct a parallel coloring algorithm with the same performance ratio, for the f irst such result. As a byproduct, we obtain a parallel approximation f or the independent set problem. (C) 1997 Academic Press.