Lovasz Test for 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. 

The main topological tool that Lovasz employed was the Borsuk-Ulam theorem. Since then, topological equivariant methods have gained ground and become part of the standard repertoire in combinatorics. 

It will be shown in Theorem 18.3 that the complexes Af G) and Bip (G) have the same simple homotopy type. This fact leads one to consider the family of Horn complexes as a natural context in which to look for further obstructions to the existence of graph homomorphisms. 

Before proceeding with the proof of Lovasz s theorem, we need the following useful lemma. 

This follows immediately by repeated application of Proposition 8.25. 

---