Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 30, 2017, 12:15 pm
Duration: 45 minutes
Location: OAT S15/S16/S17
Speaker: Charlotte Knierim
The clique chromatic number of a graph G is the minimum integer s such that we can color the vertices of G with s colors so that no maximal clique of size at least 2 is monochromatic. In this talk I will present results about the clique chromatic number of binomial random graphs. The main part of the talk will be on a result from Alon and Krivelevich where they prove that for dense binomial random graphs G=G(n,p) with p constant we have that with high probability the clique chromatic number of G is Omega(log n). Their work settles a problem of McDiarmid, Mitsche and Pralat who proved that the clique chromatic number is O(log n) with high probability.
Automatic MiSe System Software Version 1.4803M | admin login