Takahiro Matsushita
Published 2014-04-06, updated 2015-09-13Version 3
The box complex $B(G)$ is a $\mathbb{Z}_2$-poset associated with a graph $G$, which was introduced in the context of the graph coloring problem. We study the poset structure of box complex. Our main theorem states that, up to isolated vertices, the $\Z_2$-poset structure determines the original graph, and the poset structure determines its Kronecker double covering. Applying this, we have graphs which have the same box complexes as posets but have different chromatic numbers. We also mention the case of Lov\'asz's neighborhood complex $N(G)$.
Comments: 12 pages. Many typos were corrected. The paper was shortened by deleting some results easily obtained by previous works. The author decided to discuss only the case of box complexes and neighborhood complexes, and delete the general case of Hom complexes since there are no remarkable applications of them
Sidorenko's conjecture for blow-ups
A note on $\mathtt{V}$-free $2$-matchings
On the number of spanning trees in bipartite graphs
![QR code for arXiv:1404.1549 [math.CO]](http://oss.arxitics.com/images/favicon.svg)