On the game chromatic number of sparse random graphs

Alan Frieze, Simi Haber, Mikhail Lavrov

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wi…