The game chromatic number of random graphs

DOI10.1002/RSA.20179MaRDI QIDQ5454360zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tom Bohman, Alan Frieze, Benny Sudakov

Publication date 28 March 2008

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

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

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)

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.

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

Cited in

(19)

• scientific article; zbMATH DE number 7306571 (Why is no real title available?)
• 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
• Indicated coloring of graphs
• PSPACE-completeness of two graph coloring games
• scientific article; zbMATH DE number 5670857 (Why is no real title available?)

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)