A short proof of a conjecture on the connectivity of graph coloring complexes
HTML articles powered by AMS MathViewer
- by Alexander Engström PDF
- Proc. Amer. Math. Soc. 134 (2006), 3703-3705 Request permission
Abstract:
The $\mathtt {Hom}$–complexes were introduced by Lovász to study topological obstructions to graph colorings. It was conjectured by Babson and Kozlov, and proved by Čukić and Kozlov, that $\mathtt {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
- E. Babson, D.N. Kozlov, Complexes of graph homomorphisms. Israel J. Math. 152 (2006), 285–312.
- A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
- A. Björner, L. Lovász, S. T. Vrećica, and R. T. Živaljević, Chessboard complexes and matching complexes, J. London Math. Soc. (2) 49 (1994), no. 1, 25–39. MR 1253009, DOI 10.1112/jlms/49.1.25
- Sonja Lj. Čukić and Dmitry N. Kozlov, Higher connectivity of graph coloring complexes, Int. Math. Res. Not. 25 (2005), 1543–1562. MR 2152894, DOI 10.1155/IMRN.2005.1543
- Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90–145. MR 1612391, DOI 10.1006/aima.1997.1650
- 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.
Additional Information
- Alexander Engström
- Affiliation: Department of Computer Science, Eidgenössische Technische Hochschule, Zürich, Switzerland
- Email: engstroa@inf.ethz.ch
- 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
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 134 (2006), 3703-3705
- MSC (2000): Primary 57M15, 05C15
- DOI: https://doi.org/10.1090/S0002-9939-06-08417-6
- MathSciNet review: 2240686