Homology, Homotopy and Applications

Volume 19 (2017)

Number 2

Box complexes and homotopy theory of graphs

Pages: 175 – 197

DOI: https://dx.doi.org/10.4310/HHA.2017.v19.n2.a10


Takahiro Matsushita (Department of Mathematics, Kyoto University, Kitashirakawa Oiwake-cho Sakyo-ku, Kyoto, Japan)


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.


graph, neighborhood complex, box complex, Hom complex, model category

2010 Mathematics Subject Classification

Primary 55U10. Secondary 05C15.

Received 13 June 2016

Received revised 21 December 2016

Published 18 October 2017