Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
By Dmitry N. Kozlov. 2005
65 citations recorded by the source corpus.
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 \cite{BK03a,BK03b,BK03c,CK1,CK2,K4,K5}. The structural theory is developed and put in the historical context, culminating in the proof of the Lov\'asz Conjecture, which can be stated as follows: For a graph G, such that the complex Hom(C_{2r+1},G) is k-connected for some integers r>0 and k>-2, we have \chi(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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/aad4fc7ea7fb3c02a5121318e23e7163630df6cb
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Mathematical Physics
Citations in the corpus
- A simple proof for folds on both sides in complexes of graph homomorphisms (2004, background): “C O ] 3 D ec 2 We also give an easy inductive proof of the only nonelementary fact which we use for our arguments: if ϕ is a closure operator on P , then ∆(P ) collapses onto ∆(ϕ(P )).”