The game chromatic number of random graphs

2007/07/03 by Tom Bohman, Alan Frieze, Bohman, Tom +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.0707.0465

openalex publication_date 2007/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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. In this paper we analyze the asymptotic behavior of this parameter for a random graph G_n,p. We show that with high probability the game chromatic number of G_n,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs.

Cited by

• The domatic number game played on graphs

Related

• The game chromatic number of dense random graphs
• On the game chromatic number of sparse random graphs
• The game chromatic number of a random hypergraph
• Total Game Coloring of Graphs
• The Eternal Game Chromatic Number of a Graph