The Game Chromatic Number of Dense Random Graphs
The Game Chromatic Number of Dense Random Graphs
Suppose that two players take turns coloring the vertices of a given graph G with k colors. In each move the current player colors a vertex such that neighboring vertices get different colors. The first player wins this game if and only if at the end, all vertices are colored. …