Consider the following one-player game. Starting with the empty graph on nvertices, in every step r new edges are drawn uniformly at random and inserted intothe current graph. These edges have to be colored immediately with r availablecolors, subject to the restriction that each color is used for exactly one of theseedges. The player's goal is to avoid creating a monochromatic copy of some fixedgraph F for as long as possible. We prove explicit threshold functions for the duration of this game for an arbi-trary number of colors r and a large class of graphs F. This extends earlier workfor the case r = 2 by Marciniszyn, Mitsche, and Stojakovic. We also prove a similarthreshold result for the vertex-coloring analogue of this game.
展开▼
