Abstract. E. Babson and D. N. Kozlov defined the graph homomorphisms complex $\mathop{\rm Hom} (H,G)$ in [1]. This construction was introduced by Lovász to give lower bounds for the chromatic number of a graph. In this paper we prove that $\mathop{\rm Hom} (K_l,KG_{m,n})$ is homotopy equivalent to a wedge of $(m-nl)$-dimensional spheres, where $K_l$ is a complete graph and $KG_{m,n}$ is a Kneser graph. As a corollary we prove that, for a graph $G$, and positive integers $n$ and $l\ge2$, $\mathop{\rm ind} (\mathop{\rm Hom} (K_l,G))+ln\leq\chi _n(G)$.

AMS Subject Classification (1991): 55P15, 05C15

Keyword(s): graph homomorphisms complex, multichromatic number, topological lower bound

Received July 29, 2009, and in revised form January 19, 2010. (Registered under 88/2009.)