Remote Access Electronic Research Announcements

Electronic Research Announcements

ISSN 1079-6762



Topological obstructions to graph colorings

Authors: Eric Babson and Dmitry N. Kozlov
Journal: Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 61-68
MSC (2000): Primary 05C15; Secondary 57M15, 55N91, 55T99
Published electronically: August 26, 2003
MathSciNet review: 2029466
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For any two graphs $G$ and $H$ Lovász 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ász concerning these complexes with $G$ a cycle of odd length. More specifically, we show that

If $\text{\tt Hom}\,(C_{2r+1},G)$ is $k$-connected, then $\chi(G)\geq k+4$.

Our actual statement is somewhat sharper, as we find obstructions already in the nonvanishing of powers of certain Stiefel-Whitney classes.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Electronic Research Announcements of the American Mathematical Society with MSC (2000): 05C15, 57M15, 55N91, 55T99

Retrieve articles in all journals with MSC (2000): 05C15, 57M15, 55N91, 55T99

Additional Information

Eric Babson
Affiliation: Department of Mathematics, University of Washington, Seattle, Washington

Dmitry N. Kozlov
Affiliation: Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden
Address at time of publication: Department of Mathematics, University of Bern, Switzerland

Keywords: Graphs, chromatic number, graph homomorphisms, Stiefel-Whitney classes, equivariant cohomology, free action, spectral sequences, obstructions, Kneser conjecture, Borsuk-Ulam theorem
Received by editor(s): May 17, 2003
Published electronically: August 26, 2003
Communicated by: Ronald L. Graham
Article copyright: © Copyright 2003 American Mathematical Society