Complexes of graph homomorphisms

Details Complexes of graph homomorphisms Complexes of graph homomorphisms

2003-10-05

arxiv.org/abs/math/0310056v4

Israel Journal of Mathematics 152 (2006), pp. 285-312

Mathematics

Combinatorics

This is the first part of the series of papers containing the complete proofs of the results announced in "Topological obstruc

Scientific paper

$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.

Affiliated with

Also associated with

No associations

Rating

Complexes of graph homomorphisms 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 Complexes of graph homomorphisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexes of graph homomorphisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-652395