On the neighborhood complex of $\vec{s}$-stable Kneser graphs

Hamid Reza Daneshpajouh, József Osztényi

Published 2019-04-17Version 1

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.