Box complexes and homotopy theory of graphs

Abstract

We introduce a model structure on the category of graphs, which is Quillen equivalent to the category of ${\mathbb{Z}}_2$-spaces. A weak equivalence is a graph homomorphism which induces a ${\mathbb{Z}}_2$-homotopy equivalence between their box complexes. The box complex is a ${\mathbb{Z}}_2$-space associated to a graph, considered in the context of the graph coloring problem. In the proof, we discuss the universality problem of the Hom complex.

arXiv comment21 pages, final version, to be published in Homotopy, Homology and Applications

References in corpus (1)

• Homotopy types of Hom complexes of graphs