|
A short proof of a conjecture on the connectivity of graph coloring complexes
Author(s):
Alexander
Engström
Journal:
Proc. Amer. Math. Soc.
134
(2006),
3703-3705.
MSC (2000):
Primary 57M15, 05C15
Posted:
June 12, 2006
Retrieve article in:
PDF
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:
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
Copyright of article:
Copyright
2006,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org