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
DOI:
https://doi.org/10.1090/S1079-6762-03-00112-4
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 $\mathtt {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 $\operatorname {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.
Knes M. Kneser, Aufgabe 300, Jber. Deutsch. Math.-Verein. 58 (1955).
- L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324. MR 514625, DOI 10.1016/0097-3165(78)90022-5
- Daniel Quillen, Higher algebraic $K$-theory. I, Algebraic $K$-theory, I: Higher $K$-theories (Proc. Conf., Battelle Memorial Inst., Seattle, Wash., 1972) Lecture Notes in Math., Vol. 341, Springer, Berlin, 1973, pp. 85–147. MR 0338129
- Günter M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), no. 3, 671–691. MR 1893009, DOI 10.1007/s002220100188
Knes M. Kneser, Aufgabe 300, Jber. Deutsch. Math.-Verein. 58 (1955).
Lo L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324.
Qu D. Quillen, Higher algebraic K-theory I, Lecture Notes in Math., vol. 341, Springer-Verlag, 1973, pp. 77–139.
Zi02 G. M. Ziegler, Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math. 147 (2002), 671–691.
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
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
