On the Chromatic Number of Grassmann Graphs

In this paper we study the chromatic number of the Grassmann graphs $J_q(n,m)$. We show that ${\left(\genfrac{}{}{0px}{}{n-m+1}{1}\right)}_q\le \chi (J_q(n,m))\le {\left(\genfrac{}{}{0px}{}{n}{1}\right)}_q$, which is analogous to the best-known bounds for the chromatic number of the Johnson graphs $J(n,m)$. When $m=2$, determining $\chi (J_q(n,2))$ is equivalent to determining the smallest number of partial line parallelisms that one can partition the lines of PG$(n-1,q)$ into. We survey known results about line parallelisms and their implications for $\chi (J_q(n,2))$. Finally, we prove that when $q$ is any power of two, and $n$ is any even integer, then $\chi (J_q(n,2))<2{\left(\genfrac{}{}{0px}{}{n-1}{1}\right)}_q$.