Homotopy types of Hom complexes of graphs

Abstract

The Hom complex $\mathrm{Hom}(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{Hom}(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{Hom}(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{Hom}(T,G)$ and $\mathrm{Hom}(T,H)$ are homotopy equivalent but $\chi (H)$ is much larger than $\chi (G)$. The equivariant homotopy type of $\mathrm{Hom}(T,G)$ is also considered.

arXiv comment13 pages, final version. In the present version, the proofs are simplified

Cited by in corpus (1)

• Box complexes and homotopy theory of graphs