Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

This journal is archived by the American Mathematical Society. The master copy is available at http://www.ams.org/era/

For any two graphs $G$ and $H$ Lov\'asz has defined a cell complex $\text{\tt Hom}\, (G,H)$ having in mind the general program that the algebraic invariants of these complexes should provide obstructions to graph colorings. Here we announce the proof of a conjecture of Lov\'asz concerning these complexes with $G$ a cycle of odd length. More specifically, we show that \medskip \begin{quote} {\it If $\thom(C_{2r+1},G)$ is $k$-connected, then $\chi(G)\geq k+4$.} \end{quote} \medskip Our actual statement is somewhat sharper, as we find obstructions already in the nonvanishing of powers of certain Stiefel-Whitney classes.

Copyright 2003 American Mathematical Society

TeX source (30.9K)
DVI (44.5K)
PostScript (128.0K)

Article Info

• ERA Amer. Math. Soc. 09 (2003), pp. 61-68
• Publisher Identifier: S 1079-6762(03)00112-4
• 2000 Mathematics Subject Classification. Primary 05C15; Secondary 57M15, 55N91, 55T99
• Key words and phrases. Graphs, chromatic number, graph homomorphisms, Stiefel-Whitney classes, equivariant cohomology, free action, spectral sequences, obstructions, Kneser conjecture, Borsuk-Ulam theorem
• Received by editors May 17, 2003
• Posted on August 26, 2003
• Communicated by Ronald L. Graham
• Comments (When Available)

Eric Babson

Department of Mathematics, University of Washington, Seattle, Washington

E-mail address: babson@math.washington.edu

Dmitry N. Kozlov

Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden; Department of Mathematics, University of Bern, Switzerland

E-mail address: kozlov@math.kth.se, kozlov@math-stat.unibe.ch