Hom complexes and homotopy theory in the category of graphs

Details Hom complexes and homotopy theory in the category of graphs Hom complexes and homotopy theory in the category of graphs

2006-05-10

arxiv.org/abs/math/0605275v4

Mathematics

Combinatorics

28 pages, 13 figures, final version, to be published in European J. Comb

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Hom complexes and homotopy theory in the category of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hom complexes and homotopy theory in the category of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hom complexes and homotopy theory in the category of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-705925