Topology of Hom complexes and test graphs for bounding chromatic number

Research paper by Anton Dochtermann, Carsten Schultz

Indexed on: 12 Jun '12Published on: 12 Jun '12Published in: Israel Journal of Mathematics


The Hom complex of homomorphisms between two graphs was originally introduced to provide topological lower bounds on the chromatic number. In this paper we introduce new methods for understanding the topology of Hom complexes, mostly in the context of Γ-actions on graphs and posets (for some group Γ). We view the Hom(T, ⊙) and Hom(⊙, G) complexes as functors from graphs to posets, and introduce a functor (⊙)1 from posets to graphs obtained by taking atoms as vertices. Our main structural results establish useful interpretations of the equivariant homotopy type of Hom complexes in terms of spaces of equivariant poset maps and Γ-twisted products of spaces. When P:= F(X) is the face poset of a simplicial complex X, this provides a useful way to control the topology of Hom complexes. These constructions generalize those of the second author from [17] as well as the calculation of the homotopy groups of Hom complexes from [8].Our foremost application of these results is the construction of new families of test graphs with arbitrarily large chromatic number—graphs T with the property that the connectivity of Hom(T,G) provides the best possible lower bound on the chromatic number of G. In particular we focus on two infinite families, which we view as higher dimensional analogues of odd cycles. The family of spherical graphs have connections to the notion of homomorphism duality, whereas the family of twisted toroidal graphs lead us to establish a weakened version of a conjecture (due to Lovász) relating topological lower bounds on the chromatic number to maximum degree. Other structural results allow us to show that any finite simplicial complex X with a free action by the symmetric group Sn can be approximated up to Sn-homotopy equivalence as Hom(Kn,G) for some graph G; this is a generalization of the results of Csorba from [5] for the case of n = 2. We conclude the paper with some discussion regarding the underlying categorical notions involved in our study.