Lower bounds on the chromatic number of random graphs

Peter Ayre, Amin Coja-Oghlan, Catherine Greenhill

We prove that a formula predicted on the basis of non-rigorous physics arguments [Zdeborova and Krzakala: Phys. Rev. E (2007)] provides a lower bound on the chromatic number of spa…