A Note on the Warmth of Random Graphs with Given Expected Degrees

Abstract EN

We consider the random graph model G(w) for a given expected degree sequence w=(w1,w2,…,wn).

Warmth, introduced by Brightwell and Winkler in the context of combinatorial statistical mechanics, is a graph parameter related to lower bounds of chromatic number.

We present new upper and lower bounds on warmth of G(w).

In particular, the minimum expected degree turns out to be an upper bound of warmth when it tends to infinity and the maximum expected degree m=O(nα) with 0<α<1/2.