Online balanced graph avoidance games

Abstract

We introduce and study online balanced coloring games on the random graph process. The game is played by a player we call Painter. Edges of the complete graph with n vertices are introduced two at a time, in a random order. For each pair of edges, Painter immediately and irrevocably chooses one of the two possibilities to color one of them red and the other one blue. His goal is to avoid creating a monochromatic copy of a small fixed graph F for as long as possible. We show that the duration of the game is determined by a threshold function mH = mH (n) for certain graph-theoretic structures, e.g., cycles. That is, for every graph H in this family, Painter will asymptotically almost surely (a.a.s.) lose the game after m = ω (mH) edge pairs in the process. On the other hand, there exists an essentially optimal strategy: if the game lasts for m = o (mH) moves, Painter can a.a.s. successfully avoid monochromatic copies of H. Our attempt is to determine the threshold function for several classes of graphs. © 2007 Elsevier Ltd. All rights reserved.