Proof of the Lovasz Conjecture

Details Proof of the Lovasz Conjecture Proof of the Lovasz Conjecture

2004-02-24

arxiv.org/abs/math/0402395v3

Annals of Mathematics, submitted 2/2/2004, accepted 28/7/2005, http://www.math.princeton.edu/~annals/issues/2005/AnnalsAccepte

Mathematics

Combinatorics

Revised and updated version

Scientific paper

To any two graphs G and H one can associate a cell complex Hom(G,H) by taking all graph multihomorphisms from G to H as cells. In this paper we prove the Lovasz Conjecture which states that if Hom(C_{2r+1},G) is k-connected, then \chi(G)\geq k+4, where r,k\in Z, r\geq 1, k\geq -1, and C_{2r+1} denotes the cycle with 2r+1 vertices. The proof requires analysis of the complexes Hom(C_{2r+1},K_n). For even n, the obstructions to graph colorings are provided by the presence of torsion in H^*(Hom(C_{2r+1},K_n);Z). For odd n, the obstructions are expressed as vanishing of certain powers of Stiefel-Whitney characteristic classes of Hom(C_{2r+1},K_n), where the latter are viewed as $\zz$-spaces with the involution induced by the reflection of C_{2r+1}.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-352616