






















In this paper we study the chromatic number of the Grassmann graphs $J_q(n, m)$. We show that $\binom{n-m+1}{1}_q \leq χ(J_q(n, m)) \leq \binom{n}{1}_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\binom{n-1}{1}_q$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。