Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 12, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Michael Belfrage
Consider the following one-player game played on a graph with n vertices: one at the time the edges of the complete graph are presented in a uniformly at random order, and as each edge appears, the player (henceforth called Painter) immediately has to color it with one of $r$ available colors. Painter's aim is to color as many edges as possible without creating a monochromatic copy of some fixed given graph $G$.
Many variations and instances of this game have been studied previously. Here, we study the case when the fixed graph $G$ is a tree. We show that the (asymptotic) number of edges Painter is typically able to color is directly linked to the existence of a winning strategy for an adversary in a variant of the corresponding deterministic two-player game. Moreover, we show that even in the simplest nontrivial case where $G$ is a path, the natural greedy strategy (as discussed elsewhere) is not always an optimal strategy for Painter.
Joint work with Torsten Mütze and Reto Spöhel.
Automatic MiSe System Software Version 1.4803M | admin login