Colouring Lines in Projective Space
| dc.creator | Chowdhury, Ameera | |
| dc.creator | Godsil, Chris | |
| dc.creator | Royle, Gordon | |
| dc.date | 2005-07-15 | |
| dc.date.accessioned | 2026-07-07T05:21:45Z | |
| dc.date.available | 2026-07-07T05:21:45Z | |
| dc.description | 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 $α\capβ$ 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 $q^2+q$ when $v=4$ and $(q^{v-1}-1)/(q-1)$ when $v > 4$. In both cases we characterise the minimal colourings. | |
| dc.description | 19 pages; to appear in J. Combinatorial Theory, Series A | |
| dc.identifier | https://arxiv.org/abs/math/0507319 | |
| dc.identifier | http://arxiv.org/abs/math/0507319 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/75799 | |
| dc.subject | Combinatorics | |
| dc.subject | 05c15; 51e99 | |
| dc.title | Colouring Lines in Projective Space | |
| dc.type | text |