{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/285427"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/285427","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Extremal and Structural Problems of Graphs","abstract":"In this dissertation, we are interested in studying several parameters of graphs and understanding their extreme values. We begin in Chapter~$2$ with a question on edge colouring. When can a partial proper edge colouring of a graph of maximum degree $\\Delta$ be extended to a proper colouring of the entire graph using an `optimal' set of colours? Albertson and Moore conjectured this is always possible provided no two precoloured edges are within distance $2$. The main result of Chapter~$2$ comes close to proving this conjecture. Moreover, in Chapter~$3$, we completely answer the previous question for the class of planar graphs. Next, in Chapter~$4$, we investigate some Ramsey theoretical problems. We determine exactly what minimum degree a graph $G$ must have to guarantee that, for any two-colouring of $E(G)$, we can partition $V(G)$ into two parts where each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct colours. The following saturation problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger is considered in Chapter~$5$. Given a graph $H$ and a set of colours $\\{1,2,\\ldots,t\\}$ (for some integer $t\\geq |E(H)|$), we define $sat_{t}(n, R(H))$ to be the minimum number of $t$-coloured edges in a graph on $n$ vertices which does not contain a rainbow copy of $H$ but the addition of any non-edge in any colour from $\\{1,2,\\ldots,t\\}$ creates such a copy. We prove several results concerning these extremal numbers. In particular, we determine the correct order of $sat_{t}(n, R(H))$, as a function of $n$, for every connected graph $H$ of minimum degree greater than $1$ and for every integer $t\\geq e(H)$. In Chapter~$6$, we consider the following question: under what conditions does a Hamiltonian graph on $n$ vertices possess a second cycle of length at least $n-o(n)$? We prove that the `weak' assumption of a minimum degree greater or equal to $3$ guarantees the existence of such a long cycle. We solve two problems related to majority colouring in Chapter~$7$. This topic was recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number $k$, the smallest positive integer $m = m(k)$ such that every digraph can be coloured with $m$ colours, where each vertex has the same colour as at most a proportion of $\\frac{1}{k}$ of its out-neighbours. Our main theorem states that $m(k) \\in \\{2k-1, 2k\\}$. We study the following problem, raised by Caro and Yuster, in Chapter~$8$. Does every graph $G$ contain a `large' induced subgraph $H$ which has $k$ vertices of degree exactly $\\Delta(H)$? We answer in the affirmative an approximate version of this question. Indeed, we prove that, for every $k$, there exists $g(k)$ such that any $n$ vertex graph $G$ with maximum degree $\\Delta$ contains an induced subgraph $H$ with at least $n-g(k)\\sqrt{\\Delta}$ vertices such that $V(H)$ contains at least $k$ vertices of the same degree $d \\ge \\Delta(H)-g(k)$. This result is sharp up to the order of $g(k)$. %Subsequently, we investigate a concept called $\\textit{path-pairability}$. A graph is said to be path-pairable if for any pairing of its vertices there exist a collection of edge-disjoint paths routing the the vertices of each pair. A question we are concerned here asks whether every planar path pairable graph on $n$ vertices must possess a vertex of degree linear in $n$. Indeed, we answer this question in the affirmative. We also sketch a proof resolving an analogous question for graphs embeddable on surfaces of bounded genus. Finally, in Chapter~$9$, we move on to examine $k$-linked tournaments. A tournament $T$ is said to be $k$-linked if for any two disjoint sets of vertices $\\{x_1,\\ldots ,x_k\\}$ and $\\{y_1,\\dots,y_k\\}$ there are directed vertex disjoint paths $P_1,\\dots, P_k$ such that $P_i$ joins $x_i$ to $y_i$ for $i = 1,\\ldots, k$. We prove that any $4k$ strongly-connected tournament with sufficiently large minimum out-degree is $k$-linked. This result comes close to proving a conjecture of Pokrovskiy.","abstract_html":"In this dissertation, we are interested in studying several parameters of graphs and understanding their extreme values. We begin in Chapter~$2$ with a question on edge colouring. When can a partial proper edge colouring of a graph of maximum degree $\\Delta$ be extended to a proper colouring of the entire graph using an `optimal' set of colours? Albertson and Moore conjectured this is always possible provided no two precoloured edges are within distance $2$. The main result of Chapter~$2$ comes close to proving this conjecture. Moreover, in Chapter~$3$, we completely answer the previous question for the class of planar graphs. Next, in Chapter~$4$, we investigate some Ramsey theoretical problems. We determine exactly what minimum degree a graph $G$ must have to guarantee that, for any two-colouring of $E(G)$, we can partition $V(G)$ into two parts where each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct colours. The following saturation problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger is considered in Chapter~$5$. Given a graph $H$ and a set of colours $\\{1,2,\\ldots,t\\}$ (for some integer $t\\geq |E(H)|$), we define satt(n, R(H)) to be the minimum number of $t$-coloured edges in a graph on $n$ vertices which does not contain a rainbow copy of $H$ but the addition of any non-edge in any colour from $\\{1,2,\\ldots,t\\}$ creates such a copy. We prove several results concerning these extremal numbers. In particular, we determine the correct order of satt(n, R(H)), as a function of $n$, for every connected graph $H$ of minimum degree greater than $1$ and for every integer $t\\geq e(H)$. In Chapter~$6$, we consider the following question: under what conditions does a Hamiltonian graph on $n$ vertices possess a second cycle of length at least $n-o(n)$? We prove that the `weak' assumption of a minimum degree greater or equal to $3$ guarantees the existence of such a long cycle. We solve two problems related to majority colouring in Chapter~$7$. This topic was recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number $k$, the smallest positive integer $m = m(k)$ such that every digraph can be coloured with $m$ colours, where each vertex has the same colour as at most a proportion of $\\frac{1}{k}$ of its out-neighbours. Our main theorem states that $m(k) \\in \\{2k-1, 2k\\}$. We study the following problem, raised by Caro and Yuster, in Chapter~$8$. Does every graph $G$ contain a `large' induced subgraph $H$ which has $k$ vertices of degree exactly $\\Delta(H)$? We answer in the affirmative an approximate version of this question. Indeed, we prove that, for every $k$, there exists $g(k)$ such that any $n$ vertex graph $G$ with maximum degree $\\Delta$ contains an induced subgraph $H$ with at least $n-g(k)\\sqrt{\\Delta}$ vertices such that $V(H)$ contains at least $k$ vertices of the same degree $d \\ge \\Delta(H)-g(k)$. This result is sharp up to the order of $g(k)$. %Subsequently, we investigate a concept called path-pairability. A graph is said to be path-pairable if for any pairing of its vertices there exist a collection of edge-disjoint paths routing the the vertices of each pair. A question we are concerned here asks whether every planar path pairable graph on $n$ vertices must possess a vertex of degree linear in $n$. Indeed, we answer this question in the affirmative. We also sketch a proof resolving an analogous question for graphs embeddable on surfaces of bounded genus. Finally, in Chapter~$9$, we move on to examine $k$-linked tournaments. A tournament $T$ is said to be $k$-linked if for any two disjoint sets of vertices \\{x1,\\ldots ,xk\\} and \\{y1,\\dots,yk\\} there are directed vertex disjoint paths P1,\\dots, Pk such that Pi joins xi to yi for $i = 1,\\ldots, k$. We prove that any $4k$ strongly-connected tournament with sufficiently large minimum out-degree is $k$-linked. This result comes close to proving a conjecture of Pokrovskiy.","abstract_has_math":true,"creators":["Ferra Gomes de Almeida Girão , António José"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Bollobás, Béla"],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-03-30","date_published":"2019-03-30","updated_at":"2026-07-22T22:24:13Z","subjects":["Combinatorics","Extremal Graph Theory","Structural Graph Theory","Ramsey theory","Extremal Combinatorics"],"languages":["en"],"rights":[],"rights_urls":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6d37d43c-dead-401a-8265-c3ce730ed82c/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.32787","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Bollobás, Béla"]},{"key":"dc:creator","label":"Author","values":["Ferra Gomes de Almeida Girão , António José"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2019-03-30"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/285427"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorics","Extremal Graph Theory","Structural Graph Theory","Ramsey theory","Extremal Combinatorics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6d37d43c-dead-401a-8265-c3ce730ed82c/download","https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.17863/CAM.32787"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/82b8f577-0f82-439d-a5d3-ee3a5770e5ad/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In this dissertation, we are interested in studying several parameters of graphs and understanding their extreme values. We begin in Chapter~$2$ with a question on edge colouring. When can a partial proper edge colouring of a graph of maximum degree $\\Delta$ be extended to a proper colouring of the entire graph using an `optimal' set of colours? Albertson and Moore conjectured this is always possible provided no two precoloured edges are within distance $2$. The main result of Chapter~$2$ comes close to proving this conjecture. Moreover, in Chapter~$3$, we completely answer the previous question for the class of planar graphs. Next, in Chapter~$4$, we investigate some Ramsey theoretical problems. We determine exactly what minimum degree a graph $G$ must have to guarantee that, for any two-colouring of $E(G)$, we can partition $V(G)$ into two parts where each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct colours. The following saturation problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger is considered in Chapter~$5$. Given a graph $H$ and a set of colours $\\{1,2,\\ldots,t\\}$ (for some integer $t\\geq |E(H)|$), we define $sat_{t}(n, R(H))$ to be the minimum number of $t$-coloured edges in a graph on $n$ vertices which does not contain a rainbow copy of $H$ but the addition of any non-edge in any colour from $\\{1,2,\\ldots,t\\}$ creates such a copy. We prove several results concerning these extremal numbers. In particular, we determine the correct order of $sat_{t}(n, R(H))$, as a function of $n$, for every connected graph $H$ of minimum degree greater than $1$ and for every integer $t\\geq e(H)$. In Chapter~$6$, we consider the following question: under what conditions does a Hamiltonian graph on $n$ vertices possess a second cycle of length at least $n-o(n)$? We prove that the `weak' assumption of a minimum degree greater or equal to $3$ guarantees the existence of such a long cycle. We solve two problems related to majority colouring in Chapter~$7$. This topic was recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number $k$, the smallest positive integer $m = m(k)$ such that every digraph can be coloured with $m$ colours, where each vertex has the same colour as at most a proportion of $\\frac{1}{k}$ of its out-neighbours. Our main theorem states that $m(k) \\in \\{2k-1, 2k\\}$. We study the following problem, raised by Caro and Yuster, in Chapter~$8$. Does every graph $G$ contain a `large' induced subgraph $H$ which has $k$ vertices of degree exactly $\\Delta(H)$? We answer in the affirmative an approximate version of this question. Indeed, we prove that, for every $k$, there exists $g(k)$ such that any $n$ vertex graph $G$ with maximum degree $\\Delta$ contains an induced subgraph $H$ with at least $n-g(k)\\sqrt{\\Delta}$ vertices such that $V(H)$ contains at least $k$ vertices of the same degree $d \\ge \\Delta(H)-g(k)$. This result is sharp up to the order of $g(k)$. %Subsequently, we investigate a concept called $\\textit{path-pairability}$. A graph is said to be path-pairable if for any pairing of its vertices there exist a collection of edge-disjoint paths routing the the vertices of each pair. A question we are concerned here asks whether every planar path pairable graph on $n$ vertices must possess a vertex of degree linear in $n$. Indeed, we answer this question in the affirmative. We also sketch a proof resolving an analogous question for graphs embeddable on surfaces of bounded genus. Finally, in Chapter~$9$, we move on to examine $k$-linked tournaments. A tournament $T$ is said to be $k$-linked if for any two disjoint sets of vertices $\\{x_1,\\ldots ,x_k\\}$ and $\\{y_1,\\dots,y_k\\}$ there are directed vertex disjoint paths $P_1,\\dots, P_k$ such that $P_i$ joins $x_i$ to $y_i$ for $i = 1,\\ldots, k$. We prove that any $4k$ strongly-connected tournament with sufficiently large minimum out-degree is $k$-linked. This result comes close to proving a conjecture of Pokrovskiy."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["f16fab56ad1a5a5cb745ee9b4d4853e9","87eda9de84448d1f82354d60eee3eb5f"]},{"key":"dc:title","label":"Title","values":["Extremal and Structural Problems of Graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Bollobás, Béla"],"dc:creator":["Ferra Gomes de Almeida Girão , António José"],"dc:date.issued":["2019-03-30"],"dc:description.abstract":["In this dissertation, we are interested in studying several parameters of graphs and understanding their extreme values. We begin in Chapter~$2$ with a question on edge colouring. When can a partial proper edge colouring of a graph of maximum degree $\\Delta$ be extended to a proper colouring of the entire graph using an `optimal' set of colours? Albertson and Moore conjectured this is always possible provided no two precoloured edges are within distance $2$. The main result of Chapter~$2$ comes close to proving this conjecture. Moreover, in Chapter~$3$, we completely answer the previous question for the class of planar graphs. Next, in Chapter~$4$, we investigate some Ramsey theoretical problems. We determine exactly what minimum degree a graph $G$ must have to guarantee that, for any two-colouring of $E(G)$, we can partition $V(G)$ into two parts where each part induces a connected monochromatic subgraph. This completely resolves a conjecture of Bal and Debiasio. We also prove a `covering' version of this result. Finally, we study another variant of these problems which deals with coverings of a graph by monochromatic components of distinct colours. The following saturation problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger is considered in Chapter~$5$. Given a graph $H$ and a set of colours $\\{1,2,\\ldots,t\\}$ (for some integer $t\\geq |E(H)|$), we define $sat_{t}(n, R(H))$ to be the minimum number of $t$-coloured edges in a graph on $n$ vertices which does not contain a rainbow copy of $H$ but the addition of any non-edge in any colour from $\\{1,2,\\ldots,t\\}$ creates such a copy. We prove several results concerning these extremal numbers. In particular, we determine the correct order of $sat_{t}(n, R(H))$, as a function of $n$, for every connected graph $H$ of minimum degree greater than $1$ and for every integer $t\\geq e(H)$. In Chapter~$6$, we consider the following question: under what conditions does a Hamiltonian graph on $n$ vertices possess a second cycle of length at least $n-o(n)$? We prove that the `weak' assumption of a minimum degree greater or equal to $3$ guarantees the existence of such a long cycle. We solve two problems related to majority colouring in Chapter~$7$. This topic was recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number $k$, the smallest positive integer $m = m(k)$ such that every digraph can be coloured with $m$ colours, where each vertex has the same colour as at most a proportion of $\\frac{1}{k}$ of its out-neighbours. Our main theorem states that $m(k) \\in \\{2k-1, 2k\\}$. We study the following problem, raised by Caro and Yuster, in Chapter~$8$. Does every graph $G$ contain a `large' induced subgraph $H$ which has $k$ vertices of degree exactly $\\Delta(H)$? We answer in the affirmative an approximate version of this question. Indeed, we prove that, for every $k$, there exists $g(k)$ such that any $n$ vertex graph $G$ with maximum degree $\\Delta$ contains an induced subgraph $H$ with at least $n-g(k)\\sqrt{\\Delta}$ vertices such that $V(H)$ contains at least $k$ vertices of the same degree $d \\ge \\Delta(H)-g(k)$. This result is sharp up to the order of $g(k)$. %Subsequently, we investigate a concept called $\\textit{path-pairability}$. A graph is said to be path-pairable if for any pairing of its vertices there exist a collection of edge-disjoint paths routing the the vertices of each pair. A question we are concerned here asks whether every planar path pairable graph on $n$ vertices must possess a vertex of degree linear in $n$. Indeed, we answer this question in the affirmative. We also sketch a proof resolving an analogous question for graphs embeddable on surfaces of bounded genus. Finally, in Chapter~$9$, we move on to examine $k$-linked tournaments. A tournament $T$ is said to be $k$-linked if for any two disjoint sets of vertices $\\{x_1,\\ldots ,x_k\\}$ and $\\{y_1,\\dots,y_k\\}$ there are directed vertex disjoint paths $P_1,\\dots, P_k$ such that $P_i$ joins $x_i$ to $y_i$ for $i = 1,\\ldots, k$. We prove that any $4k$ strongly-connected tournament with sufficiently large minimum out-degree is $k$-linked. This result comes close to proving a conjecture of Pokrovskiy."],"dc:format.checksum.md5":["f16fab56ad1a5a5cb745ee9b4d4853e9","87eda9de84448d1f82354d60eee3eb5f"],"dc:identifier.doi":["10.17863/CAM.32787"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/82b8f577-0f82-439d-a5d3-ee3a5770e5ad/download"],"dc:language":["en"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/285427"],"dc:rights":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6d37d43c-dead-401a-8265-c3ce730ed82c/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["Combinatorics","Extremal Graph Theory","Structural Graph Theory","Ramsey theory","Extremal Combinatorics"],"dc:title":["Extremal and Structural Problems of Graphs"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:13Z"}