“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 2-stable 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 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 →s-stable Kneser graph KG(n, k)→s−stab as the induced subgraph of the Kneser graph KG(n, k) on →s-stable vertices. And we prove, for given an integer vector →s=(s1,…, sk) and n ≥ ∑i=1k−1si+2 where si ≥ 2 for i ≠ k and sk ∈ {1,2}, the neighborhood complex of KG(n, k)→s−stab is homotopy equivalent to the (n−∑i=1k−1si−2)-sphere. In particular, this implies that χ(KG(n, k)→s−stab) = n−∑i=1k−1si 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.
Download TeX format |
|
| back to top | |
