Box complexes and homotopy theory of graphs

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.

Keywords

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

2010 Mathematics Subject Classification

Primary 55U10. Secondary 05C15.

Full Text (PDF format)

Received 13 June 2016

Received revised 21 December 2016

Published 18 October 2017