Balanced online Ramsey games in random graphs
The electronic journal of combinatorics, Tome 16 (2009) no. 1
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 Marciniszyn, Mitsche, and Stojaković. We also prove a similar threshold result for the vertex-coloring analogue of this game.
@article{10_37236_100,
author = {Anupam Prakash and Reto Sp\"ohel and Henning Thomas},
title = {Balanced online {Ramsey} games in random graphs},
journal = {The electronic journal of combinatorics},
year = {2009},
volume = {16},
number = {1},
doi = {10.37236/100},
zbl = {1178.05087},
url = {http://geodesic.mathdoc.fr/articles/10.37236/100/}
}
Anupam Prakash; Reto Spöhel; Henning Thomas. Balanced online Ramsey games in random graphs. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/100
Cité par Sources :