Skip to Main content Skip to Navigation
Conference papers

Balanced Avoidance Games on Random Graphs

Abstract : We introduce and study balanced online graph avoidance 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 revealed two at a time in a random order. In each move, Painter immediately and irrevocably decides on a balanced coloring of the new edge pair: either the first edge is colored red and the second one blue or vice versa. His goal is to avoid a monochromatic copy of a given fixed graph $H$ in both colors for as long as possible. The game ends as soon as the first monochromatic copy of $H$ has appeared. We show that the duration of the game is determined by a threshold function $m_H = m_H(n)$. More precisely, Painter will asymptotically almost surely (a.a.s.) lose the game after $m = \omega (m_H)$ edge pairs in the process. On the other hand, there is an essentially optimal strategy, that is, if the game lasts for $m = o(m_H)$ moves, then Painter will a.a.s. successfully avoid monochromatic copies of H using this strategy. Our attempt is to determine the threshold function for certain graph-theoretic structures, e.g., cycles.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 2:59:09 PM
Last modification on : Thursday, May 27, 2021 - 1:54:05 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:13:04 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01184443, version 1



Martin Marciniszyn, Dieter Mitsche, Miloš Stojaković. Balanced Avoidance Games on Random Graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.329-334. ⟨hal-01184443⟩



Record views


Files downloads