In this paper we study a pair of numerical parameters associated to a graph G. On the one hand, we consider the (topological) connectivity of the polyhedral complex Hom(K2,G), a space of homomorphisms from a edge K2 into G. This approach dates back to the neighborhood complexes introduced by Lovász in his proof of the Kneser conjecture. In another direction we study the warmth ζ(G) of a graph G, a parameter introduced by Brightwell and Winkler based on the asymptotic behavior of d-branching walks in G and inspired by constructions in statistical physics. Both the warmth of G and the connectivity of Hom(K2,G) provide lower bounds on the chromatic number of G. Here we seek to relate these two constructions, and in particular we provide evidence for the conjecture that the warmth of a graph G is always less than three plus the connectivity of Hom(K2,G). We succeed in establishing a first nontrivial case of the conjecture, by showing that ζ(G)≤3 if Hom(K2,G) has an infinite first homology group. We also calculate warmth for a family of ‘twisted toroidal’ graphs that are important extremal examples in the context of Hom complexes. Finally we show that ζ(G)≤n−1 if a graph G does not have the complete bipartite graph Ka,b for a+b=n. This provides an analogue for a similar result in the context of Hom complexes.
- Chromatic number
- Combinatorial statistical mechanics
- Graph homomorphism
- Neighborhood complex
- Topological methods