Extremal Theory of Graph Minors and Related Topics

The core of this thesis are new asymptotically tight bounds for the maximum average degree of a graph with no H minor for several new classes of graph H. Chapter 2 derives an upper bound for almost all graphs H with t vertices and average degree d for a new sparse regime with d = t^o(1). Chapter 3 extends these results to use additional structural information and treat certain vertices of the graph differently to others. This derives an improved upper bound for sparse structured graphs. We also construct a lower bound for almost all such graphs. These themes are continued in Chapter 5, which introduces the new notion of containing a multigraph as a minor. The extremal function is asymptotically derived for multigraphs rKt, consisting of t vertices and all pairs having multiplicity r, in two regimes corresponding to r = ω(log t) or r = o(log t). A lower bound is proven for all r which I conjecture is tight. In Chapter 6 we then consider the extremal function for fixed, small multigraphs as minors, including when the host graph is permitted to contain double edges. In Chapter 4 we consider a related problem of finding minors in bipartite subgraphs of G, where instead of the average degree the Hadwiger number is instead fixed. We find an asymptotic result for the largest bipartite minor. We also prove bounds for the topological analogue of this question. Moving further from minors, Chapter 7 considers the method of Entropy Compression. The main result is a construction showing that Entropy Compression, or the Rosenfeld/ Wanless-Wood framework, provides a best possible bound on the block-average degree of a graph not containing an independent transversal. We also provide a new proof of this matching upper bound, which under a very slightly stronger condition gives an efficient algorithm for constructing such a transversal. Finally, Chapter 8 considers Gallai colourings, and more concretely which sequences of colour class sizes can be realized in a Gallai colouring. We prove a new restriction on such sequences, as well as two results showing certain sequences can be realized in this fashion.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2022

Author dc:creator

• Wales, Matthew

Advisor dc:contributor.advisor

• Thomason, Andrew

• combinatorics
• graph theory
• graph minors

Licence

• https://www.rioxx.net/licenses/all-rights-reserved/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.86668

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/339260