Balanced online Ramsey games in random graphs
type: Item
instance of: scholarly article
title: Balanced online Ramsey games in random graphs
zbMATH Open document ID: 1178.05087
author: Anupam Prakash
author: Reto Spöhel
author: Henning Thomas
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/117295
full work available at URL: v16i1r11.html
review text: Summary: Consider the following one-player game. Starting with the empty graph on \(n\) vertices, in every step \(r\) new edges are drawn uniformly at random and inserted into the current graph. These edges have to be colored immediately with \(r\) available colors, subject to the restriction that each color is used for exactly one of these edges. The player's goal is to avoid creating a monochromatic copy of some fixed graph \(F\) for as long as possible. We prove explicit threshold functions for the duration of this game for an arbitrary number of colors \(r\) and a large class of graphs \(F\). This extends earlier work for the case \(r=2\) by \textit{M. Marciniszyn}, \textit{D. Mitsche}, and \textit{M. Stojaković} [``Online balanced graph avoidance games'', Eur. J. Comb. 28, No.\,8, 2248--2263 (2007; Zbl 1126.05050)]. We also prove a similar threshold result for the vertex-coloring analogue of this game.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 5541076
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5541076