ICS Theory Group

ICS 269, Spring 1998: Theory Seminar

1 May 1998:
Parallel and On-Line Graph Coloring
Brad Hutchings, ICS, UC Irvine

Brad described results from a paper by Magnus M. Halldorsson in Journal of Algorithms 23, 265-280 (1987). The approximate coloring algorithms in the paper work by forming a maximal partial coloring with a limited number of colors. The remaining uncolored vertices are partitioned according to their adjacencies with members of one color class, forming a collection of subgraphs with smaller chromatic number. These subgraphs are then colored independently and recursively. Halldorsson shows that this approach leads to approximation ratios of O(n / log n), not only sequentially but also in the parallel and on-line settings.