Hom complexes and homotopy theory in the category of graphs
| dc.creator | Dochtermann, Anton | |
| dc.date | 2006-05-10 | |
| dc.date | 2008-07-07 | |
| dc.date.accessioned | 2026-07-07T09:48:29Z | |
| dc.date.available | 2026-07-07T09:48:29Z | |
| dc.description | 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á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. | |
| dc.description | 28 pages, 13 figures, final version, to be published in European J. Comb | |
| dc.identifier | https://arxiv.org/abs/math/0605275 | |
| dc.identifier | http://arxiv.org/abs/math/0605275 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/164232 | |
| dc.subject | Combinatorics | |
| dc.subject | Algebraic Topology | |
| dc.subject | 05C30 (Primary); 55P10, 57M15, 18D15 (Secondary) | |
| dc.title | Hom complexes and homotopy theory in the category of graphs | |
| dc.type | text |