Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes (Q2502966)

The author proves that for a graph \(G\), the neighborhood complex \(\mathcal N(G)\) and (the barycentric subdivision of) the polyhedral complex \(\text{Hom}(K_2,G)\) of graph homomorphisms have the same simple homotopy type, that is, one can be obtained from the other by a finite sequence of collapses and anti-collapses. Here \(K_2\) denotes the complete graph on two nodes.