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

Abstract

In 2002, A. Björner and M. de Longueville showed the neighborhood complex of the $2$-stable Kneser graph ${KG(n,k)}_{2-\text{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ényi. Combining this result with the famous Lová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}-\text{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,\dots ,s_k)$ and $n\ge {\sum }_{i=1}^{k-1}{s}_i+2$ where $s_i\ge 2$ for $i\ne k$ and $s_k\in \{1,2\}$, the neighborhood complex of ${KG(n,k)}_{\vec{s}-\text{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}-\text{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.

References in corpus (2)

• Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes
• On the chromatic number of almost s-stable Kneser graphs