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 deficit. 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.
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Member of collection