%0 Journal Article
%T A Note on the Warmth of Random Graphs with Given Expected Degrees
%A Yilun Shang
%J International Journal of Mathematics and Mathematical Sciences
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/749856
%X We consider the random graph model for a given expected degree sequence . 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 . 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 with . 1. Introduction Let be a graph with vertex set and edge set . For graphs and , a function is said to be a graph homomorphism [1] if it induces a map between edges . Denote by the set of all homomorphisms of a graph to a graph . Let denote the -branching rooted tree (with the root having degree ); see Figure 1 for an illustration. A map in is said to be cold if there is a vertex of such that for any no agrees with on the vertices at distance from the root but has . We say that is -warm if does not contain any cold maps. Moreover, the warmth, , of £¿is defined to be the largest for which is -warm. By definition, for any finite and connected graph , and if and only if £¿is bipartite. Figure 1: The labeling of vertices for the 3-branching rooted tree. Warmth is a graph parameter introduced by Brightwell and Winkler [2] in the context of combinatorial statistical physics. It is closely related to the chromatic number of a graph, which is the smallest positive integer that is not a root of the chromatic polynomial (see, e.g., [3]). It was shown that [2, Theorem 5.1] for any unlooped graph £¿the warmth of is at most its chromatic number. A natural question to ask would be what the warmth of a graph looks like in a typical graph or random graphs £¿[4]. Recently, Fadnavis and Kahle £¿[5] established some upper and lower bounds for Erd£¿s-R¨¦nyi random graphs as well as random regular graphs. The main finding is that warmth is often much smaller than chromatic number for random graphs. We mention that most of the parameters examined in random graph theory are monotone with respect to the addition (or deletion) of edges [4, 6]. However, warmth is not such a parameter, which makes it difficult to study in random graph settings. In this paper, motivated by the work of [5], we study the upper and lower bounds of warmth in a general random graph model . For a given sequence , is defined as follows. Each potential edge between vertices and is chosen with probability and is independent of other edges, where Here, we assume that and define . An immediate consequence of (1) is that the expected degree at a vertex is exactly £¿[7]. Hence, £¿is the
%U http://www.hindawi.com/journals/ijmms/2014/749856/