{
  "id": "1404.1549",
  "version": "v3",
  "published": "2014-04-06T06:46:04.000Z",
  "updated": "2015-09-13T14:50:04.000Z",
  "title": "Box complex and Kronecker double covering",
  "authors": [
    "Takahiro Matsushita"
  ],
  "comment": "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",
  "categories": [
    "math.CO",
    "math.AT"
  ],
  "abstract": "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)$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-04-16T08:23:03.000Z",
      "title": "Complexes of bipartite graphs, neighborhood complexes, and box complexes",
      "abstract": "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) \\not\\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.",
      "comment": "19 pages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2015-09-13T14:50:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "neighborhood complexes",
      "box complexes",
      "bipartite graph",
      "isomorphic",
      "hom complexes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.1549M"
    }
  }
}