On the neighborhood complex of s→-stable Kneser graphs

In 2002, Björner and de Longueville showed the neighborhood complex of the 2-stable Kneser graph KG(n,k)_2−stab has the same homotopy type as the (n−2k)-sphere. A short time ago, an analogous result about the homotopy type of the neighborhood complex of almost s-stable Kneser graph has been announced by the second author. Combining this result with the famous Lovász's topological lower bound on the chromatic number of graphs yielded a new way for determining the chromatic number of these graphs which was determined a bit earlier by Chen. In this paper we present a common generalization of the mentioned results. For given an integer vector s→=(s₁,…,s_k), first we define s→-stable Kneser graph KG(n,k)_s→−stab as an induced subgraph of the Kneser graph KG(n,k). Then, we show that the neighborhood complex of KG(n,k)_s→−stab has the same homotopy type as the n−∑_i=1^k−1s_i−2-sphere for some specific values of the parameter s→. In particular, this implies that χKG(n,k)_s→−stab=n−∑_i=1^k−1s_i for those parameters. Moreover, as a simple corollary of this result, we give a lower bound on the chromatic number of 3-stable Kneser graphs which is just one less than the number conjectured in this regard.