Lovasz complex

Proposition 13.16 was proved by the author in [Ko06c], though the fact that the neighborhood complex is homotopy equivalent to the Lovasz complex was well known before that. Theorem 13.18 was also proved by the author in [Ko06cj. 

The molecular walk count is related to - moleeular branehing and size, and in general to the - molecular complexity of the graph. In fact, it was found that mwe is directly related to the Lovasz-Pelikan index, i.e. the largest eigenvalue of the adjacency matrix [Cvetkovic and Gutman, 1977]... 

The original Lovasz test, which was based on computing the connectivity of a certain abstract simplicial complex associated to the graph in question, also has high computational complexity, since determining the triviality of the homotopy groups is an extremely hard problem, even in low dimensions. 

Lovasz has introduced the neighborhood complex N G) as a part of his topological approach to the resolution of the Kneser conjecture. The hard part of the proof is to show the inequality x En,k) > n — 2k + 2, and Lovasz s idea was to use the connectivity information of the topological space Af G) to find obstructions to the vertex-colorability of G. More precisely, he proved the following statement. 

The Lovasz conjecture (here Theorem 19.15) was from the very beginning an important motivation for developing the theory of Horn complexes. It was originally settled by Babson and the author in a series of papers [BK03, BK06, BK04]. 

---