Achlioptas and Naor determined the chromatic number of the random graph G(n,p) with average degree
np=O(1) up to an additive error of one. In this talk I'm going to show how their techniques can be
combined with other methods such as concentration results to obtain the chromatic number for
np less than n^{1/4}.
This is joint work with Konstantinos Panagiotou and Angelika Steger.
The ACO Seminar (2010-2011)