Box complex and Kronecker double covering
Takahiro Matsushita · arXiv (Cornell University) · 2014
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)$.