Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, August 30, 2012, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Andreas Noever
Consider the following one player game: We start with an empty graph on n vertices. Each round an edge is selected u.a.r. and added to the graph. The player has to color it immediately ('online') with one of the r available colors. For how long can she avoid a monochromatic copy of a fixed graph F? For the two color case thresholds are known for a large number of classes including cycles and cliques. We prove a tight upper bound for triangles and an arbitrary number of colors.
The thesis was supervised by Luca Gugelmann and Angelika Steger.
Automatic MiSe System Software Version 1.4803M | admin login