Topological colouring bounds and graph structure

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2011-06-06
Authors/Contributors
Abstract
Lovasz invoked topological colouring bounds in proving Kneser's Conjecture. Subsequently, numerous applications of topological techniques to graph colouring problems have arisen. However, even today, little is known about how to construct a graph with a particular topological colouring bound, or about the structure of such graphs. The aim of this thesis is to remedy this de ficit. First, we will perform a review of topological techniques used in bounding the chromatic number and discuss constructing graphs with particular topological colouring bounds. Then we will derive necessary conditions for a graph to attain a particular topological colouring bound, and use these conditions to analyze the structure of such graphs. In particular, we provide support for some open problems in graph theory by verifying the problems under additional assumptions on topological colouring bounds. We also discuss the relationship between colour critical graphs with tight topological colouring bounds and quadrangulations of surfaces.
Document
Identifier
etd6792
Copyright statement
Copyright is held by the author.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Member of collection
Attachment Size
etd6792_NSinger.pdf 580.3 KB