On the Game Chromatic Number of Sparse Random Graphs

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 $\chi_g(G)$ is the...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2013-01, Vol.27 (2), p.768-790
Main Authors: Frieze, Alan, Haber, Simcha, Lavrov, Mikhail
Format: Article
Language:English
Subjects:
Algorithms
Asymptotic properties
Games
Graphs
Integers
Mathematical analysis
Players
Random variables
Strategy
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 $\chi_g(G)$ is the minimum $k$ for which the first player has a winning strategy. The paper [T. Bohman, A. M. Frieze, and B. Sudakov, Random Structures Algorithms, 32 (2008), pp. 223--235] began the analysis of the asymptotic behavior of this parameter for a random graph $G_{n,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 with high probability (w.h.p.) $c_1\chi(G_{n,p})\leq \chi_g(G_{n,p})\leq c_2\chi(G_{n,p})$ for some absolute constants $1
ISSN:0895-4801
1095-7146
DOI:10.1137/120861953