|
A short proof of a conjecture on the connectivity of graph coloring complexes
Author:
Alexander Engström
Journal:
Proc. Amer. Math. Soc. 134 (2006), 3703-3705
MSC (2000):
Primary 57M15, 05C15
Posted:
June 12, 2006
MathSciNet review:
2240686
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: The  -complexes were introduced by Lovász to study topological obstructions to graph colorings. It was conjectured by Babson and Kozlov, and proved by Cukic and Kozlov, that  is  -connected, where  is the maximal degree of a vertex of  , and  the number of colors. We give a short proof of the conjecture.
References
- 1.
E. Babson, D.N. Kozlov, Complexes of graph homomorphisms. Israel J. Math. 152 (2006), 285-312.
- 2.
A. Björner, Topological Methods, in: ``Handbook of Combinatorics'' (eds. R. Graham, M. Grötschel, and L. Lovász), North-Holland, 1995, 1819-1872. MR 1373690 (96m:52012)
- 3.
A. Björner, L. Lovász, S.T. Vrecica, R.T. Zivaljevic, Chessboard complexes and matching complexes, J. London Math. Soc. (2) 49 (1994), 25-49. MR 1253009 (95c:52021)
- 4.
S. Lj. Cukic, D.N. Kozlov, Higher connectivity of graph coloring complexes, Int. Math. Res. Notices. 2005:25 (2005), 1543-1562.MR 2152894
- 5.
R. Forman, Morse theory for cell complexes, Adv. Math. 134, no. 1, (1998), 90-145.MR 1612391 (99b:57050)
- 6.
D.N. Kozlov, Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes, 67 pages, to appear in Geometric Combinatorics, IAS/Park City Mathematics Series 14, American Mathematical Society, Providence, RI; Institute for Advanced Study (IAS), Princeton, NJ.
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2000):
57M15,
05C15
Retrieve articles in all journals
with MSC (2000):
57M15,
05C15
Additional Information
Alexander Engström
Affiliation:
Department of Computer Science, Eidgenössische Technische Hochschule, Zürich, Switzerland
Email:
engstroa@inf.ethz.ch
DOI:
http://dx.doi.org/10.1090/S0002-9939-06-08417-6
PII:
S 0002-9939(06)08417-6
Keywords:
Graph homomorphisms,
$k$-connectivity,
{\tt Hom}-complexes,
graph coloring complexes
Received by editor(s):
May 31, 2005
Received by editor(s) in revised form:
July 6, 2005
Posted:
June 12, 2006
Additional Notes:
This research was supported by ETH and Swiss National Science Foundation Grant PP002-102738/1
Communicated by:
Paul Goerss
Article copyright:
© Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain after
28 years from publication.
|
