On the neighborhood complex of [formula omitted]-stable Kneser graphs.

In 2002, Björner and de Longueville showed the neighborhood complex of the 2-stable Kneser graph K G (n , k) 2 − s t a b has the same homotopy type as the (n − 2 k) -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 1 , ... , s k) , first we define s → -stable Kneser graph K G (n , k) s → − s t a b as an induced subgraph of the Kneser graph K G (n , k). Then, we show that the neighborhood complex of K G (n , k) s → − s t a b has the same homotopy type as the n − ∑ i = 1 k − 1 s i − 2 -sphere for some specific values of the parameter s →. In particular, this implies that χ K G (n , k) s → − s t a b = n − ∑ i = 1 k − 1 s 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. [ABSTRACT FROM AUTHOR]