Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

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
Published electronically: June 12, 2006
MathSciNet review: 2240686
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The $ {\tt Hom}$-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 $ {\tt Hom}(G,K_n)$ is $ (n-d-2)$-connected, where $ d$ is the maximal degree of a vertex of $ G$, and $ n$ the number of colors. We give a short proof of the conjecture.


References [Enhancements On Off] (What's this?)


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
Published electronically: 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 28 years after publication.