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. https://resolver.caltech.edu/CaltechAUTHORS:20170408-204250029
![]() |
PDF
- Accepted Version
See Usage Policy. 157kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170408-204250029
Abstract
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: |
| |||||||||
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 | |||||||||
DOI: | 10.1016/j.jcta.2005.01.010 | |||||||||
Record Number: | CaltechAUTHORS:20170408-204250029 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170408-204250029 | |||||||||
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, https://doi.org/10.1016/j.jcta.2005.01.010. (http://www.sciencedirect.com/science/article/pii/S0097316505000336) | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 76391 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | 1Science Import | |||||||||
Deposited On: | 30 Mar 2018 23:22 | |||||||||
Last Modified: | 15 Nov 2021 16:59 |
Repository Staff Only: item control page