Warmth and connectivity of neighborhood complexes of graphs

preprint2021arXivOpen access

Abstract

In this paper we study a pair of numerical parameters associated to a graph GG. One the one hand, one can construct Hom(K2,G)\text{Hom}(K_2, G), a space of homomorphisms from a edge K2K_2 into GG and study its (topological) connectivity. This approach dates back to the neighborhood complexes introduced by Lovász in his proof of the Kneser conjecture. In another direction Brightwell and Winkler introduced a graph parameter called the warmth ζ(G)ζ(G) of a graph GG, based on asymptotic behavior of dd-branching walks in GG and inspired by constructions in statistical physics. Both the warmth of GG and the connectivity of Hom(K2,G)\text{Hom}(K_2,G) provide lower bounds on the chromatic number of GG. Here we seek to relate these two constructions, and in particular we provide evidence for the conjecture that the warmth of a graph GG is always less than three plus the connectivity of Hom(K2,G)\text{Hom}(K_2, G). We succeed in establishing a first nontrivial case of the conjecture, by showing that ζ(G)≤3ζ(G) \leq 3 if Hom(K2,G)\text{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\text{Hom} complexes. Finally we show that ζ(G)≤n−1ζ(G) \leq n-1 if a graph GG does not have the complete bipartite graph Ka,bK_{a,b} for a+b=na+b=n. This provides an analogue for a similar result in the context of Hom\text{Hom} complexes.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.