The game chromatic number of dense random graphs

MaRDI QIDQ490261zbMATH OpenFDO

Authors Ralph Keusch, Angelika Steger

Publication date 22 January 2015

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

Full work available at URL https://arxiv.org/abs/1406.7126, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p47

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

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)

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})$.

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

Cites work

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

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)