“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16493  


Abstract:  
In 2002, A. Björner and M. de Longueville showed the neighborhood complex of the 2stable 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 sstable 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 →sstable Kneser graph KG(n, k)_{→s−stab} as the induced subgraph of the Kneser graph KG(n, k) on →sstable vertices. And we prove, for given an integer vector →s=(s_{1},…, s_{k}) and n ≥ ∑_{i=1}^{k−1}s_{i}+2 where s_{i} ≥ 2 for i ≠ k and s_{k} ∈ {1,2}, the neighborhood complex of KG(n, k)_{→s−stab} is homotopy equivalent to the (n−∑_{i=1}^{k−1}s_{i}−2)sphere. In particular, this implies that χ(KG(n, k)_{→s−stab}) = n−∑_{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 3stable kneser graphs with at most one error.
Download TeX format 

back to top 