The game chromatic number of random graphs

DOI10.1002/RSA.20179zbMATH Open1139.05017DBLPjournals/rsa/BohmanFS08arXiv0707.0465OpenAlexW2963016487WikidataQ57401486 ScholiaQ57401486MaRDI QIDQ5454360FDOQ5454360

Authors: Tom Bohman, Alan Frieze, Benny Sudakov 

Publication date: 28 March 2008

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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 chi_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.

Full work available at URL: https://arxiv.org/abs/0707.0465

Recommendations

• The game chromatic number of a random hypergraph
• The game chromatic number of dense random graphs
• The game chromatic and chromatic number of some graphs
• The eternal game chromatic number of random graphs
• On the game chromatic number of sparse random graphs
• The chromatic number of random graphs
• The chromatic number of random graphs
• Game chromatic number of some network graphs
• scientific article; zbMATH DE number 398953
• A bound for the game chromatic number of graphs

zbMATH Keywords

random graphchromatic numbergame chromatic numberrandom bipartite graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Cited In (19)

• Title not available (Why is that?)
• A new upper bound on the game chromatic index of graphs
• Game chromatic index of graphs with given restrictions on degrees
• Majority coloring game
• The incidence game chromatic number of paths and subgraphs of wheels
• On the game chromatic number of sparse random graphs
• The connected greedy coloring game
• The eternal game chromatic number of random graphs
• The game chromatic number of a random hypergraph
• The difference between game chromatic number and chromatic number of graphs
• On monotonicity in maker-breaker graph colouring games
• On graphs with maximum difference between game chromatic number and chromatic number
• Game-perfect digraphs
• The game chromatic number of dense random graphs
• \textsf{PSPACE}-hardness of variants of the graph coloring game
• PSPACE-hardness of two graph coloring games
• PSPACE-completeness of two graph coloring games
• Indicated coloring of graphs
• Title not available (Why is that?)

This page was built for publication: The game chromatic number of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5454360)