Homotopy types of Hom complexes of graphs

The Hom complex $\mathrm{H}\mathrm{o}\mathrm{m}(T,G)$ of graphs is a CW-complex associated to a pair of graphs $T$ and $G$, considered in the graph coloring problem. It is known that certain homotopy invariants of $\mathrm{H}\mathrm{o}\mathrm{m}(T,G)$ give lower bounds for the chromatic number of $G$. For a fixed finite graph $T$, we show that there is no homotopy invariant of $\mathrm{H}\mathrm{o}\mathrm{m}(T,G)$ which gives an upper bound for the chromatic number of $G$. More precisely, for a non-bipartite graph $G$, we construct a graph $H$ such that $\mathrm{H}\mathrm{o}\mathrm{m}(T,G)$ and $\mathrm{H}\mathrm{o}\mathrm{m}(T,H)$ are homotopy equivalent but $\chi (H)$ is much larger than $\chi (G)$. The equivariant homotopy type of ${\rm Hom}(T,G)$ is also considered.