Complexes of graph homomorphisms (Q2382336)

For any two graphs \(G\) and \(H\) there is a polyhedral complex \({\Hom}(G,H)\), the \textit{Hom-complex} of \(G\) and \(H\), whose vertices are the graph homomorphisms from \(G\) to \(H\). Especially interesting are the complexes \({\Hom}(G,K_n)\) where \(K_n\) is the complete graph on \(n\) nodes. This complex is non-empty if and only if \(G\) admits a proper coloring of its nodes with \(n\) colors. In the paper under review the authors prove a number of combinatorial and topological results about Hom-complexes. In particular, they show that \({\Hom}(K_2,G)\) is homotopy equivalent to the neighborhood complex of \(G\). The degree of connectedness of the latter is known to form an obstruction to the colorability of \(G\) from \textit{L. Lovász}' solution of the Kneser conjecture [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)]. Moreover, it is proved that \({\Hom}(K_m,K_n)\) is homotopy equivalent to a wedge of \((n-m)\)-dimensional spheres, and a recurrence relation is given for their number. Other results involve the computation of homotopy types of Hom-complexes from finite forests to complete graphs. The techniques developed in this paper were applied in the authors' proof [Ann. Math. (2) 165, No.~3, 965--1007 (2007; Zbl 1132.05019)] of a conjecture of Lovász.