Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 06, 2014, 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 graphs. For more than two colors no tight bounds were known. We prove a tight upper bound for an arbitrary number of colors for a class of graphs which includes cycles and cliques.
Automatic MiSe System Software Version 1.4803M | admin login