| Affiliation: | (1) Department of Mathematics, Royal Institute of Technology, S–100 44 Stockholm, Sweden;(2) Freie Universität Berlin, Fachbereich Mathematik, Arnimallee 2-6, 14195 Berlin, Germany |
| Abstract: | It is shown that the neighborhood complexes of a family ofvertex critical subgraphs of Kneser graphs—the stable Knesergraphs introduced by L. Schrijver—are spheres up to homotopy.Furthermore, it is shown that the neighborhood complexes of asubclass of the stable Kneser graphs contain the boundaries ofassociahedra (simplicial complexes encoding triangulations of apolygon) as a strong deformation retract.* The first author was partially supported by theGöran Gustafsson Foundation for Research in NaturalSciences and Medicine. The second author was supported by the graduateschool  Algorithmische Diskrete Mathematik , which is funded bythe Deutsche Forschungsgemeinschaft, grant GRK 219/3. The DAADpartially supported a stay at KTH, Stockholm, in December 1998,where this work was done: DAAD program AZ 313/S-PPP |
