Colouring lines in projective space

A Chowdhury, C Godsil, G Royle - Journal of Combinatorial Theory, Series …, 2006 - Elsevier
Journal of Combinatorial Theory, Series A, 2006Elsevier
Let V be a vector space of dimension v over a field of order q. The q-Kneser graph has the k-
dimensional subspaces of V as its vertices, where two subspaces α and β are adjacent if
and only if α∩ β is the zero subspace. This paper is motivated by the problem of determining
the chromatic numbers of these graphs. This problem is trivial when k= 1 (and the graphs
are complete) or when v< 2k (and the graphs are empty). We establish some basic theory in
the general case. Then specializing to the case k= 2, we show that the chromatic number is …
Let V be a vector space of dimension v over a field of order q. The q-Kneser graph has the k-dimensional subspaces of V as its vertices, where two subspaces α and β are adjacent if and only if α∩β is the zero subspace. This paper is motivated by the problem of determining the chromatic numbers of these graphs. This problem is trivial when k=1 (and the graphs are complete) or when v<2k (and the graphs are empty). We establish some basic theory in the general case. Then specializing to the case k=2, we show that the chromatic number is q2+q when v=4 and (qv-1-1)/(q-1) when v>4. In both cases we characterise the minimal colourings.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果