For positive integers $n\geq 2k$, it is known that the chromatic number of the [Kneser graph](https://arxiv.org/pdf/1803.04342.pdf) $K\_{n,k}$ is $n-2k+2$. Moreover, the Schrijver graph $S\_{n,k}$ (definition in the same link), which is a subgraph of $K\_{n,k}$, also has chromatic number $n-2k+2$. The number of vertices of $S\_{n,k}$ is $\binom{n-k+1}{k}$.


Is it known whether there is a subgraph of $K\_{n,k}$ with chromatic number $n-2k+2$ whose number of vertices is polynomial in $n$ and $k$?



Kneser subgraph with high chromatic number
The general answer is **no**, at least when $n$ is close to $2k$.


Theorem 3 in [this paper](https://arxiv.org/abs/1201.3271) shows that a graph with odd girth $\geq 2d+1$ and chromatic number $>m$ contains more than
$$
 \frac{(m+d)(m+d+1)\dots(m+2d-1)}{2^{d-1}d^d}
$$
vertices. The parameters for the Kneser graph $K\_{n,k}$ are $m=n-2k+1$ and $d=\bigl\lceil\frac k{n-2k}\bigr\rceil$, so, say, for $n\approx 2k+\sqrt k$ the bound is already exponential in $\sqrt k$.


