Proof of the Lovasz conjecture

• 成果类型: Article
• 署名作者: Babson, Eric; Kozlov, Dmitry N.
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2007.165.965
• 发表日期: 2007
• 页码: 965-1007
• 关键词: complexes

摘要

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