On the diameter of Schrijver graphs

Abstract

For $k\ge 1$ and $n\ge 2k$, the well known Kneser graph $\mathrm{KG}(n,k)$ has all $k$-element subsets of an $n$-element set as vertices; two such subsets are adjacent if they are disjoint. Schrijver constructed a vertex-critical subgraph $\mathrm{SG}(n,k)$ of $\mathrm{KG}(n,k)$ with the same chromatic number. In this paper, we compute the diameter of the graph $\mathrm{SG}(2k+r,k)$ with $r\ge 1$. We obtain an exact value of the diameter of $\mathrm{SG}(2k+r,k)$ when $r\in \{1,2\}$ or when $r\ge k-3$. For the remained cases, when $3\le r\le k-4$, we obtain that the diameter of $\mathrm{SG}(2k+r,k)$ belongs to the integer interval $[\mathrm{4..}k-r-1]$.