math.CO math.AT
On the neighborhood complex of vec s stable Kneser graphs. In 2002, A. Bj "orner and M. de Longueville showed the neighborhood complex of the 2 stable Kneser graph KG(n, k) 2 textit 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 J. Oszt ' e nyi. Combining this result with the famous Lov ' a sz's topological lower bound on the chromatic number of graphs has been yielded a new way for determining the chromatic number of these graphs which was determined a bit earlier by P. Chen. In this paper we present a common generalization of the mentioned results. We will define the vec s stable Kneser graph KG(n, k) vec s textit stab as the induced subgraph of the Kneser graph KG(n, k) on vec s stable vertices. And we prove, for given an integer vector vec s (s 1, ldots, s k) and n geq sum i 1 k 1 s i 2 where s i geq2 for i neq k and s k in 1,2 , the neighborhood complex of KG(n, k) vec s textit stab is homotopy equivalent to the left(n sum i 1 k 1 s i 2 right) sphere. In particular, this implies that chi left( KG(n, k) vec s textit stab right) n sum i 1 k 1 s i for the mentioned parameters. Moreover, as a simple corollary of the previous result, we will determine the chromatic number of 3 stable kneser graphs with at most one error.