"Coloring Random Graphs in Polynomial Expected Time."

Martin Fürer, C. R. Subramanian, C. E. Veni Madhavan (1993)
a service of Schloss Dagstuhl - Leibniz Center for Informatics