On the chromatic number of \(q\)-Kneser graphs (Q690656)

This is a very interesting paper that contains strong results that are outcome of difficult computations. The \(q\)-analog \(qK_{n:k}\) of the Kneser graph has the \(k\)-dimensional subspaces of an \(n\)-dimensional vector space over \(\mathrm{GF}(q)\) as vertices with two vertices adjacent if the corresponding subspaces have trivial intersection. This paper studies the chromatic number of \(qK_{2k:k}\) and shows that the chromatic number equals \(q^k + q^{k - 1}\) when \(k = 3\) and also when \(k < q{\log q} - q\). The technique of proof is based on the largest coclique in a \(q\)-Kneser graph which is the dual of the Erdős-Ko-Rado system, and in the situation under consideration, this amounts to taking all the \(k\)-dimensional subspaces of a hyperplane (i.e. a \((2k - 1)\)-dimensional subspace). The second largest conjectured coclique is given by Hilton and Milner and is considerably more technical in its description. These two largest cocliques are used in proving the results in this paper. The paper also makes a detailed and interesting analysis of the case \(qK_{6:3}\).