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.0022 seconds