Complexes of graph homomorphisms

Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K _m, K_n) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ ₁ ^k (Hom(K _m, G))≠0, thenχ(G)≥k+m; here ℤ₂-action is induced by the swapping of two vertices inK _m, and ϖ₁ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K _n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K _n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.