2005/05/26 by Kozlov, Dmitry N.
#05C15 #55T99 #57M15 #68R10 #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.math/0505563
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. Here, we survey the study of the Hom-complexes, and the ways these can be used to obtain lower bounds for the chromatic numbers of graphs, presented in a recent series of papers \citeBK03a,BK03b,BK03c,CK1,CK2,K4,K5. The structural theory is developed and put in the historical context, culminating in the proof of the Lovász 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>0 and k>-2, we have χ(G)>k+3. Beyond the, more customary in this area, cohomology groups, the algebro-topological concepts involved are spectral sequences and Stiefel-Whitney characteristic classes. Complete proofs are included for all the new results appearing in this survey for the first time.