The game chromatic number of random graphs

Tom Bohman, Alan Frieze, Benny Sudakov

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…