The Chromatic Number of the $q$-Kneser Graph for $q\ge 5$

Abstract

We obtain a new weak Hilton-Milner type result for intersecting families of $k$-spaces in ${\mathbb{F}}_q^{2k}$, which improves several known results. In particular the chromatic number of the $q$-Kneser graph $q{K}_{n:k}$ was previously known for $n>2k$ (except for $n=2k+1$ and $q=2$) or $k<q\log q-q$. Our result determines the chromatic number of $q{K}_{2k:k}$ for $q\ge 5$, so that the only remaining open cases are $(n,k)=(2k,k)$ with $q\in \{2,3,4\}$ and $(n,k)=(2k+1,k)$ with $q=2$.

arXiv comment9 pages, few typos corrected