Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
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
Email: babson@math.washington.edu

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
Email: kozlov@math.kth.se, kozlov@math-stat.unibe.ch

DOI: http://dx.doi.org/10.1090/S1079-6762-03-00112-4
PII: S 1079-6762(03)00112-4
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