Lower bounds on the chromatic number of random graphs (Q2678448)

A formula for lower bounds on the chromatic number \(\chi(G)\) of a random graph \(G\) is established using the so-called interpolation method from mathematical physics, see \textit{F. Guerra} and \textit{F. L. Toninelli} [Commun. Math. Phys. 230, No. 1, 71--79 (2002; Zbl 1004.82004)], instead of the second moment method. For random \(d\)-regular graphs, \(G(n,d)\), the formula is expressed algebraically, while for binomial random graphs (Erdős-Rényi) a variational formula is obtained. The formulas are then used to calculate explicit (and improved) lower bounds on \(\chi(G (n,d))\) with small \(d\) as well as binomial random graphs of small average degree. For large (average) degree it is shown how the new formulas can be used to easily re-derive asymptotic formulas without lengthy and complicated combinatorial arguments.