{
  "id": "math/0605275",
  "version": "v4",
  "published": "2006-05-10T18:22:09.000Z",
  "updated": "2008-07-07T09:14:54.000Z",
  "title": "Hom complexes and homotopy theory in the category of graphs",
  "authors": [
    "Anton Dochtermann"
  ],
  "comment": "28 pages, 13 figures, final version, to be published in European J. Comb",
  "categories": [
    "math.CO",
    "math.AT"
  ],
  "abstract": "We investigate a notion of $\\times$-homotopy of graph maps that is based on the internal hom associated to the categorical product in the category of graphs. It is shown that graph $\\times$-homotopy is characterized by the topological properties of the $\\Hom$ complex, a functorial way to assign a poset (and hence topological space) to a pair of graphs; $\\Hom$ complexes were introduced by Lov\\'{a}sz and further studied by Babson and Kozlov to give topological bounds on chromatic number. Along the way, we also establish some structural properties of $\\Hom$ complexes involving products and exponentials of graphs, as well as a symmetry result which can be used to reprove a theorem of Kozlov involving foldings of graphs. Graph $\\times$-homotopy naturally leads to a notion of homotopy equivalence which we show has several equivalent characterizations. We apply the notions of $\\times$-homotopy equivalence to the class of dismantlable graphs to get a list of conditions that again characterize these. We end with a discussion of graph homotopies arising from other internal homs, including the construction of `$A$-theory' associated to the cartesian product in the category of reflexive graphs.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2008-07-07T09:14:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "55P10",
      "57M15",
      "18D15"
    ],
    "keywords": [
      "homotopy theory",
      "hom complexes",
      "internal hom",
      "homotopy equivalence",
      "functorial way"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......5275D"
    }
  }
}