On the Chromatic Number of Grassmann Graphs

Jozefien D'haeseleer; Vladislav Taranchuk

paper

On the Chromatic Number of Grassmann Graphs

arXiv:2505.22055

Abstract

In this paper we study the chromatic number of the Grassmann graphs $J_{q} (n, m)$ . We show that $(1 n - m + 1)_{q} \leq χ (J_{q} (n, m)) \leq (1 n)_{q}$ , which is analogous to the best-known bounds for the chromatic number of the Johnson graphs $J (n, m)$ . When $m = 2$ , determining $χ (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 $χ (J_{q} (n, 2))$ . Finally, we prove that when $q$ is any power of two, and $n$ is any even integer, then $χ (J_{q} (n, 2)) < 2 (1 n - 1)_{q}$ .