The game chromatic number of dense random graphs

zbMATH Open1305.05144arXiv1406.7126MaRDI QIDQ490261FDOQ490261

Authors: Ralph Keusch, Angelika Steger 

Publication date: 22 January 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Suppose that two players take turns coloring the vertices of a given graph G with k colors. In each move the current player colors a vertex such that neighboring vertices get different colors. The first player wins this game if and only if at the end, all the vertices are colored. The game chromatic number $ch{i}_g(G)$ is defined as the smallest k for which the first player has a winning strategy. Recently, Bohman, Frieze and Sudakov [Random Structures and Algorithms 2008] analysed the game chromatic number of random graphs and obtained lower and upper bounds of the same order of magnitude. In this paper we improve existing results and show that with high probability, the game chromatic number $ch{i}_g(G_{n,p})$ of dense random graphs is asymptotically twice as large as the ordinary chromatic number $chi(G_{n,p})$.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The game chromatic number of random graphs
• scientific article; zbMATH DE number 398953
• On the game chromatic number of sparse random graphs
• The game chromatic number of a random hypergraph
• The difference between game chromatic number and chromatic number of graphs

zbMATH Keywords

random graphsgame chromatic number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) 2-person games (91A05) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Biased Positional Games
• The chromatic number of random graphs
• The chromatic number of random graphs
• A solution to the Box Game
• On the game chromatic number of sparse random graphs
• The game chromatic number of random graphs

Cited In (8)

• A new upper bound on the game chromatic index of graphs
• On the game chromatic number of sparse random graphs
• 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
• The game chromatic number of random graphs

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

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