Dmitry Kozlov, ETH Zürich and University of Bremen
Stiefel-Whitney characteristic classes of line bundles and graph colorings.

Combinatorics, in particular graph theory, has a rich history of being a domain of successful applications of tools from other areas of mathematics, including topological methods. In this talk I will survey the study of the Hom-complexes, and the ways these can be used to obtain lower bounds for the chromatic numbers of graphs.

The structural theory will be developed and put in the historical context, encompassing in particular the Lovasz Conjecture, which can be stated as follows:

For a graph G, such that the complex Hom(C2r+1,G) is k-connected for some integers r and k, r>0, k>-2, we know that the chromatic number of G is at least k+4.

Beyond the, more customary in this area, cohomology groups, the algebro-topological concepts involved are spectral sequences and Stiefel-Whitney characteristic classes. The latter are used to state the more general Babson-Kozlov conjecture which says:

For any graph G, we have χ(G)≥ h(Hom(C2r+1,G))+3.

Here, for a Z2-space X, h(X) denotes the maximal exponent of the non-zero power of the Stiefel-Whitney characteristic class of the associated line bundle.

I shall give an extremely short proof of the Babson-Kozlov conjecture. Furthermore, I shall describe how to use the spectral sequences to perform a complete calculation of the cohomology groups of the colorings of cycles.