This thesis was originally motivated by considering vector space analogues of problems in extremal set theory, but our main results concern colouring a graph that is intimately related to these vector space analogues. The vertices of the <em>q</em>-Kneser graph are the <em>k</em>-dimensional subspaces of a vector space of dimension <em>v</em> over F<sub><em>q</em></sub>, and two <em>k</em>-subspaces are adjacent if they have trivial intersection. The new results in this thesis involve colouring the <em>q</em>-Kneser graph when <em>k</em>=2. There are two cases. When <em>k</em>=2 and <em>v</em>=4, the chromatic number is <em>q</em><sup>2</sup>+<em>q</em>. If <em>k</em>=2 and <em>v</em>>4, the chromatic number is (<em>q</em><sup>(v-1)</sup>-1)/(<em>q</em>-1). In both cases, we characterise the minimal colourings. We develop some theory for colouring the <em>q</em>-Kneser graph in general.
Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/1026 |
Date | January 2005 |
Creators | Chowdhury, Ameerah |
Publisher | University of Waterloo |
Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
Language | English |
Detected Language | English |
Type | Thesis or Dissertation |
Format | application/pdf, 327215 bytes, application/pdf |
Rights | Copyright: 2005, Chowdhury, Ameerah. All rights reserved. |
Page generated in 0.0014 seconds