Abstract
dc:description.abstractThis 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.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2005
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Chowdhury, Ameerah
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Copyright: 2005, Chowdhury, Ameerah. All rights reserved.
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/1026