A Caltech Library Service

Colouring lines in projective space

Chowdhury, Ameera and Godsil, Chris and Royle, Gordon (2006) Colouring lines in projective space. Journal of Combinatorial Theory. Series A, 113 (1). pp. 39-52. ISSN 0097-3165. doi:10.1016/j.jcta.2005.01.010.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 q^2 + q when v = 4 and (q^(v-1) -1)/(q - 1) when v > 4. In both cases we characterise the minimal colourings.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2005 Elsevier. Received 29 September 2004, Available online 31 March 2005. The work in this paper has benefited from a number of discussions with Ada Chan.
Subject Keywords:Kneser graph; Chromatic number; Projective space
Issue or Number:1
Record Number:CaltechAUTHORS:20170408-204250029
Persistent URL:
Official Citation:Ameera Chowdhury, Chris Godsil, Gordon Royle, Colouring lines in projective space, Journal of Combinatorial Theory, Series A, Volume 113, Issue 1, 2006, Pages 39-52, ISSN 0097-3165, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:76391
Deposited By: 1Science Import
Deposited On:30 Mar 2018 23:22
Last Modified:15 Nov 2021 16:59

Repository Staff Only: item control page