Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 24, 2011, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Henning Thomas
Consider the following game: Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number of G is the minimum k for which the first player has a winning strategy. In this talk we will discuss the currently best known results about the asymptotic behavior of the game chromatic number of random graphs and random bipartite graphs.
Automatic MiSe System Software Version 1.4803M | admin login