Lower bounds on the chromatic number of random graphs
From MaRDI portal
Publication:6311568
DOI10.1007/S00493-021-4236-ZarXiv1812.09691MaRDI QIDQ6311568FDOQ6311568
Authors: Peter Ayre, Amin Coja-Oghlan, Catherine Greenhill 
Publication date: 23 December 2018
Abstract: 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 sparse random graphs. The proof is based on the interpolation method from mathematical physics. In the case of random regular graphs the lower bound can be expressed algebraically, while in the case of the binomial random we obtain a variational formula. As an application we calculate improved explicit lower bounds on the chromatic number of random graphs for small (average) degrees. Additionally, show how asymptotic formulas for large degrees that were previously obtained by lengthy and complicated combinatorial arguments can be re-derived easily from these new results.
This page was built for publication: Lower bounds on the chromatic number of random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311568)
