{
  "id": "math/0310056",
  "version": "v4",
  "published": "2003-10-05T16:31:06.000Z",
  "updated": "2005-03-26T11:24:04.000Z",
  "title": "Complexes of graph homomorphisms",
  "authors": [
    "Eric Babson",
    "Dmitry N. Kozlov"
  ],
  "comment": "This is the first part of the series of papers containing the complete proofs of the results announced in \"Topological obstructions to graph colorings\". This is the final version which is to appear in Israel J. Math., it has an updated list of references and new remarks on latest developments",
  "journal": "Israel Journal of Mathematics 152 (2006), pp. 285-312",
  "categories": [
    "math.CO",
    "math.AT"
  ],
  "abstract": "$Hom(G,H)$ is a polyhedral complex defined for any two undirected graphs $G$ and $H$. This construction was introduced by Lov\\'asz to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that $Hom(K_m,K_n)$ is homotopy equivalent to a wedge of $(n-m)$-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graph $G$, and integers $m\\geq 2$ and $k\\geq -1$, we have $\\varpi_1^k(\\thom(K_m,G))\\neq 0$, then $\\chi(G)\\geq k+m$; here $Z_2$-action is induced by the swapping of two vertices in $K_m$, and $\\varpi_1$ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of $Hom(G,H)$ induces a homotopy equivalence. It then follows that $Hom(F,K_n)$ is homotopy equivalent to a direct product of $(n-2)$-dimensional spheres, while $Hom(\\bar{F},K_n)$ is homotopy equivalent to a wedge of spheres, where $F$ is an arbitrary forest and $\\bar{F}$ is its complement.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2005-03-26T11:24:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "55P91",
      "55S35",
      "57M15"
    ],
    "keywords": [
      "graph homomorphisms",
      "homotopy equivalent",
      "dimensional spheres",
      "polyhedral complex",
      "enumeration formula"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003math.....10056B"
    }
  }
}