## Mar 16 2001:

A presentation of
"Fast distributed graph coloring in O(Delta) colors," by
Gianluca De Marco and Andrzej Pelc, from SODA 2001.

Speaker: David Goggin, ICS, UC Irvine

We consider the problem of deterministic distributed coloring of an
n-vertex graph with maximum degree 'delta', assuming that ev ery vertex
knows a priori only its own label and parameters n and 'delta.' The aim is
to get a fast algorithm using few colors. Linial showed a vertex-coloring
algorithm working in time O(log* n) and using O(Delta^2) colors. We
improve both the time and the number of colors simultaneously by showing
an algorithm working in time O(log* (n/Delta)) and using O(Delta) colors.
This is the first known O(Delta) vertex coloring distributed algorithm
which can work faster than in polylogarithmic time.