In this thesis, we study several combinatorial problems in which we aim to find upper or lower bounds on a certain quantity relating to graphs. The first problem is in Ramsey theory, while the others are in extremal graph theory.

In Chapter 2, which is joint work with Vojtěch Dvořák, we consider the Ramsey number $R(Fn)$ of the fan graph $Fn$, a graph consisting of $n$ triangles which all share a common vertex. Chen, Yu and Zhao showed that $92n-5\le R(Fn)\le 112n+6$. We build on the techniques that they used to prove the upper bound of $112n+6$, and adopt a more detailed approach to examining the structure of the graph. This allows us to improve the upper bound to $316n+15$.

In Chapter 3, we work on a problem in graph colouring. Petruševski and Škrekovski recently introduced the concept of odd colouring, and the odd chromatic number of a graph, which is the smallest number of colours in an odd colouring of that graph. They showed that planar graphs have odd chromatic number at most $9$, and this bound was improved to $8$ by Petr and Portier. We consider the odd chromatic number of toroidal graphs, which are graphs that embed into a torus. By using the discharging method, along with detailed analysis of a remaining special case, we show that toroidal graphs have odd chromatic number at most $9$.

In Chapter 4, which is joint work with Victor Souza, we consider a problem in the hypercube graph $Qn$. Huang showed that every induced subgraph of the hypercube with $2n-1+1$ vertices has maximum degree at least $\lceil n\rceil$, which resolved a major open problem in computer science known as the Sensitivity Conjecture. Huang asked whether analogous results could be obtained for larger induced subgraphs. For induced subgraphs of $Qn$ with $p2n$ vertices, we find a simple lower bound that holds for all $p$, and substantially improve this bound in the range by analysing the local structure of the graph. We also find constructions of subgraphs achieving the simple lower bound asymptotically when $p=1-1r$.