Skip to main content

Topological colouring bounds and graph structure

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
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.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Member of collection
Download file Size
etd6792_NSinger.pdf 580.3 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 0