## Archival Version

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

Topological obstructions to graph colorings
**This journal is archived by the American Mathematical
Society. The master copy is available at
http://www.ams.org/era/
**

## Topological obstructions to graph colorings

### Eric Babson and Dmitry N. Kozlov

**Abstract.**
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*

**Retrieve entire article **

#### 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`

*Electronic Research Announcements of the AMS *Home page