Colouring lines in projective space

Ameera Chowdhury, Chris Godsil, Gordon Royle

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


Let V be a vector space of dimension ν 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 ν < 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 ν = 4 and (qν-1- 1)/(q-1) when ν > 4. In both cases we characterise the minimal colourings.

Original languageEnglish (US)
Pages (from-to)39-52
Number of pages14
JournalJournal of Combinatorial Theory. Series A
Issue number1
StatePublished - Jan 2006
Externally publishedYes


  • Chromatic number
  • Kneser graph
  • Projective space


Dive into the research topics of 'Colouring lines in projective space'. Together they form a unique fingerprint.

Cite this