10.1184/R1/6478868.v1 Alan Frieze Alan Frieze Simcha Haber Simcha Haber Mikhail Lavrov Mikhail Lavrov On the Game Chromatic Number of Sparse Random Graphs Carnegie Mellon University 2014 Mathematical Sciences 2014-02-06 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/On_the_Game_Chromatic_Number_of_Sparse_Random_Graphs/6478868 <p>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 wins iff at the end of the game all the vertices of G are colored. The game chromatic number χg(G) is the minimum k for which the first player has a winning strategy. The paper [6] began the analysis of the asymptotic behavior of this parameter for a random graph Gn,p. This paper provides some further analysis for graphs with constant average degree i.e. np = O(1) and for random regular graphs. We show that w.h.p. c1χ(Gn,p) ≤ χg(Gn,p) ≤ c2χ(Gn,p) for some absolute constants 1 < c1 < c2. We also prove that if Gn,3 denotes a random n-vertex cubic graph then w.h.p. χg(Gn,3) = 4.</p>