## Abstract

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(K_{2},G), a space of homomorphisms from a edge K_{2} 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(K_{2},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(K_{2},G). We succeed in establishing a first nontrivial case of the conjecture, by showing that ζ(G)≤3 if Hom(K_{2},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 K_{a,b} for a+b=n. This provides an analogue for a similar result in the context of Hom complexes.

Original language | English |
---|---|

Pages (from-to) | 176-194 |

Number of pages | 19 |

Journal | Advances in Applied Mathematics |

Volume | 96 |

DOIs | |

Publication status | Published - 1 May 2018 |

MoE publication type | A1 Journal article-refereed |

## Keywords

- Chromatic number
- Combinatorial statistical mechanics
- Connectivity
- Graph homomorphism
- Neighborhood complex
- Topological methods
- Warmth