Graphs in higher dimensions

Mihaylov, Tsvetomir (2024). Graphs in higher dimensions. University of Birmingham. Ph.D.

Preview

Mihaylov2024PhD.pdf
Text
Available under License All rights reserved.
Download (2MB) | Preview

Abstract

The overarching theme of this thesis is exploring exciting results in graph theory and discovering suitable ways to extend them to exciting results in higher dimensions.
The first subtopic of the thesis is extending two-dimensional results about graphs into three dimensions via \(2\)-complexes. In Chapter 3, we extend the outerplanarity criterion through forbidden minors of Chartrand and Harary, in Chapter 5, we extend the Four Colour Theorem of Appel and Haken and in Chapter 6, we extend Mac Lane's Theorem.
The second subtopic of the thesis is annulus graphs, which serve as extension of both unit distance graphs and unit disc graphs in higher dimensions. The paper in Chapter 4 concerns annulus graphs in the \(d\)-dimensional spaces \(\mathbb R^d\) for \(d>0\). There, we introduce the relatively unstudied term annulus graph and show that they have a non-trivial structure. We also show that the ratio of the chromatic number to the independence number grows exponentially in the dimension of the underlying \(\mathbb{R}\)-space.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):