Topological obstructions to graph colorings
Authors:
Eric Babson and Dmitry N. Kozlov
Journal:
Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 6168
MSC (2000):
Primary 05C15; Secondary 57M15, 55N91, 55T99
Published electronically:
August 26, 2003
MathSciNet review:
2029466
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: For any two graphs and Lovász has defined a cell complex 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 a cycle of odd length. More specifically, we show that If is connected, then . Our actual statement is somewhat sharper, as we find obstructions already in the nonvanishing of powers of certain StiefelWhitney classes.
 1.
M. Kneser, Aufgabe 300, Jber. Deutsch. Math.Verein. 58 (1955).
 2.
L.
Lovász, Kneser’s conjecture, chromatic number, and
homotopy, J. Combin. Theory Ser. A 25 (1978),
no. 3, 319–324. MR 514625
(81g:05059), http://dx.doi.org/10.1016/00973165(78)900225
 3.
Daniel
Quillen, Higher algebraic 𝐾theory. I, Algebraic
𝐾theory, I: Higher 𝐾theories (Proc. Conf., Battelle
Memorial Inst., Seattle, Wash., 1972) Springer, Berlin, 1973,
pp. 85–147. Lecture Notes in Math., Vol. 341. MR 0338129
(49 #2895)
 4.
Günter
M. Ziegler, Generalized Kneser coloring theorems with combinatorial
proofs, Invent. Math. 147 (2002), no. 3,
671–691. MR 1893009
(2003d:05088), http://dx.doi.org/10.1007/s002220100188
 1.
 M. Kneser, Aufgabe 300, Jber. Deutsch. Math.Verein. 58 (1955).
 2.
 L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319324. MR 81g:05059
 3.
 D. Quillen, Higher algebraic Ktheory I, Lecture Notes in Math., vol. 341, SpringerVerlag, 1973, pp. 77139. MR 49:2895
 4.
 G. M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), 671691. MR 2003d:05088
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@mathstat.unibe.ch
DOI:
http://dx.doi.org/10.1090/S1079676203001124
PII:
S 10796762(03)001124
Keywords:
Graphs,
chromatic number,
graph homomorphisms,
StiefelWhitney classes,
equivariant cohomology,
free action,
spectral sequences,
obstructions,
Kneser conjecture,
BorsukUlam 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
