“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16493
School of Mathematics
  Title:   On the neighborhood complex of s-stable Kneser graphs
  Author(s):  Hamid Reza Daneshpajouh (Joint with J. Osztenyi)
  Status:   Published
  Journal: Discrete Math.
  Vol.:  344
  Year:  2021
  Pages:   112302
  Supported by:  IPM
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)sstab 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 ik and sk ∈ {1,2}, the neighborhood complex of KG(n, k)sstab is homotopy equivalent to the (n−∑i=1k−1si−2)-sphere. In particular, this implies that χ(KG(n, k)sstab) = 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
scroll left or right