Remote Access Proceedings of the American Mathematical Society
Green Open Access

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

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.