Proof of the Lovász conjecture
By Eric K. Babson, Dmitry N. Kozlov. 2004
146 citations recorded by the source corpus.
To any two graphs G and H one can associate a cell complex Horn (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 Horn (C 2r+1 , G) is k-connected, then Χ(G) > k + 4, where r, k ∈ Z, r > 1, k > -1, and C 2r+1 denotes the cycle with 2r+1 vertices. The proof requires analysis of the complexes Horn (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 Horn (C 2r+1 , K n ), where the latter are viewed as Z 2 -spaces with the involution induced by the reflection of C 2r+1 .
Subfields: Biophysics, Computational Theory and Mathematics, Physiology
View Paper: https://www.semanticscholar.org/paper/2d69499cc51938db37bb68ec76eadf29d64f1a4b
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Biophysics
In Computational Theory and Mathematics
In Physiology
Citations in the corpus
- Counting Graph Homomorphisms (2006, unknown): “Counting Graph Homomorphisms Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Katalin Vesztergombi February 2006 Contents”
- A simple proof for folds on both sides in complexes of graph homomorphisms (2004, background): “The spectral sequence computations in [3] required certain manipulations with the first parameter graph; these specific manipulations are usually called folds.”
- Star clusters in independence complexes of graphs (2010, unknown): “In [25], Kozlov proved the following result Theorem 4.3 ( Kozlov ) .”