Kneser conjecture

Both neighborhood and Lovfez complexes were introduced in [Lov78] in connection with the resolution of the Kneser Conjecture. 

The Kneser conjecture states that in fact equality holds. This was proved in 1978 by L. Lovasz, who used geometric obstructions of Borsuk-Ulam type to show the nonexistence of certain graph colorings. 

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. 

To finish the proof of the Kneser conjecture (Theorem 17.21), we still need to see that the neighborhood complex of Kneser graphs is sufficiently connected. In fact, it turns out that the homotopy type of these complexes can be determined precisely. 

Shortly after it was published, Lov z s resolution of the Kneser conjecture was complemented by finding a maximal subgraph having the same chromatic number as the original Kneser graph. To formulate this result, we recall that a graph G is called vertex-critical if for any vertex v G V G), we have x G) = x G-v) + l. 

---