Homotopy types of the Hom complexes of graphs

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