Complexes of bipartite graphs, neighborhood complexes, and box complexes
Takahiro Matsushita · arXiv (Cornell University) · 2014
Neighborhood complexes and box complexes of graphs were constructed in the context of the graph coloring problem. In this paper, we investigate the relationships among graphs, their Hom complexes ${\rm Hom}(K_2,G)$, and their neighborhood complexes. We prove that for graphs $G$ and $H$ having no isolated vertices, $K_2 \times G \cong K_2 \times H$ if and only if ${\rm Hom}(K_2,G) \cong {\rm Hom}(K_2,H)$ as posets. And $G \cong H$ if and only if ${\rm Hom}(G) \cong {\rm Hom}(H)$ as $\mathbb{Z}_2$-posets. In the proof of this fact, we construct a poset $B_0(X)$ for a bipartite graph $X$ satisfying ${\rm Hom}(K_2,G) \cong B_0(K_2 \times G)$ for a graph $G$ as posets. As an application, we prove that there are connected graphs $G$ and $H$ such that $\chi(G) ot\cong \chi(H)$, but ${\rm Hom}(K_2,G)$ and ${\rm Hom}(K_2,H)$ are isomorphic as posets, and their neighborhood complexes are isomorphic.