{
  "id": "1904.08219",
  "version": "v1",
  "published": "2019-04-17T12:18:49.000Z",
  "updated": "2019-04-17T12:18:49.000Z",
  "title": "On the neighborhood complex of $\\vec{s}$-stable Kneser graphs",
  "authors": [
    "Hamid Reza Daneshpajouh",
    "József Osztényi"
  ],
  "categories": [
    "math.CO",
    "math.AT"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-04-17T12:18:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "stable kneser graph",
      "neighborhood complex",
      "chromatic number",
      "homotopy type",
      "simple corollary"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}