{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/330218"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/330218","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"The Chromatic Structure of Dense Graphs","abstract":"This thesis focusses on extremal graph theory, the study of how local constraints on a graph affect its macroscopic structure. We primarily consider the chromatic structure: whether a graph has or is close to having some (low) chromatic number. Chapter 2 is the slight exception. We consider an induced version of the classical Turán problem. Introduced by Loh, Tait, Timmons, and Zhou, the induced Turán number ex(n, {H, F-ind}) is the greatest number of edges in an n-vertex graph with no copy of H and no induced copy of F. We asymptotically determine ex(n, {H, F-ind}) for H not bipartite and F neither an independent set nor a complete bipartite graph. We also improve the upper bound for ex(n, {H, K_{2, t}-ind}) as well as the lower bound for the clique number of graphs that have some fixed edge density and no induced K_{2, t}. The next three chapters form the heart of the thesis. Chapters 3 and 4 consider the Erdős-Simonovits question for locally r-colourable graphs: what are the structure and chromatic number of graphs with large minimum degree and where every neighbourhood is r-colourable? Chapter 3 deals with the locally bipartite case and Chapter 4 with the general case. While the subject of Chapters 3 and 4 is a natural local to global colouring question, it is also essential for determining the minimum degree stability of H-free graphs, the focus of Chapter 5. Given a graph H of chromatic number r + 1, this asks for the minimum degree that guarantees that an H-free graph is close to r-partite. This is analogous to the classical edge stability of Erdős and Simonovits. We also consider the question for the family of graphs to which H is not homomorphic, showing that it has the same answer. Chapter 6 considers sparse analogues of the results of Chapters 3 to 5 obtaining the thresholds at which the sparse problem degenerates away from the dense one. Finally, Chapter 7 considers a chromatic Ramsey problem first posed by Erdős: what is the greatest chromatic number of a triangle-free graph on $n$ vertices or with m edges? We improve the best known bounds and obtain tight (up to a constant factor) bounds for the list chromatic number, answering a question of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot.","abstract_html":"This thesis focusses on extremal graph theory, the study of how local constraints on a graph affect its macroscopic structure. We primarily consider the chromatic structure: whether a graph has or is close to having some (low) chromatic number. Chapter 2 is the slight exception. We consider an induced version of the classical Turán problem. Introduced by Loh, Tait, Timmons, and Zhou, the induced Turán number ex(n, {H, F-ind}) is the greatest number of edges in an n-vertex graph with no copy of H and no induced copy of F. We asymptotically determine ex(n, {H, F-ind}) for H not bipartite and F neither an independent set nor a complete bipartite graph. We also improve the upper bound for ex(n, {H, K_{2, t}-ind}) as well as the lower bound for the clique number of graphs that have some fixed edge density and no induced K_{2, t}. The next three chapters form the heart of the thesis. Chapters 3 and 4 consider the Erdős-Simonovits question for locally r-colourable graphs: what are the structure and chromatic number of graphs with large minimum degree and where every neighbourhood is r-colourable? Chapter 3 deals with the locally bipartite case and Chapter 4 with the general case. While the subject of Chapters 3 and 4 is a natural local to global colouring question, it is also essential for determining the minimum degree stability of H-free graphs, the focus of Chapter 5. Given a graph H of chromatic number r + 1, this asks for the minimum degree that guarantees that an H-free graph is close to r-partite. This is analogous to the classical edge stability of Erdős and Simonovits. We also consider the question for the family of graphs to which H is not homomorphic, showing that it has the same answer. Chapter 6 considers sparse analogues of the results of Chapters 3 to 5 obtaining the thresholds at which the sparse problem degenerates away from the dense one. Finally, Chapter 7 considers a chromatic Ramsey problem first posed by Erdős: what is the greatest chromatic number of a triangle-free graph on $n$ vertices or with m edges? We improve the best known bounds and obtain tight (up to a constant factor) bounds for the list chromatic number, answering a question of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot.","abstract_has_math":true,"creators":["Illingworth, Frederick"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Thomason, Andrew"],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-07-01","date_published":"2021-07-01","updated_at":"2026-07-22T22:24:07Z","subjects":["Extremal Graph Theory","Combinatorics","Ramsey Theory","Graph Colouring","Stability","Dense Graphs"],"languages":["eng"],"rights":[],"rights_urls":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/9cbd783e-4e0a-404f-ba8f-774f94437bfe/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[{"key":"dc:creator.authoridentifier","label":"Author Identifier","values":["0000000153502379"],"render_values":[{"text":"0000-0001-5350-2379","href":"https://orcid.org/0000-0001-5350-2379","code":true}]}]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.77660","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Thomason, Andrew"]},{"key":"dc:creator","label":"Author","values":["Illingworth, Frederick"]},{"key":"dc:creator.authoridentifier","label":"Author Identifier","values":["0000000153502379"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2021-07-01"]},{"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/330218"]},{"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":["Extremal Graph Theory","Combinatorics","Ramsey Theory","Graph Colouring","Stability","Dense Graphs"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/9cbd783e-4e0a-404f-ba8f-774f94437bfe/download","https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.17863/CAM.77660"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/7f205e4f-b3f6-4159-9a08-30b13e8a09f2/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This thesis focusses on extremal graph theory, the study of how local constraints on a graph affect its macroscopic structure. We primarily consider the chromatic structure: whether a graph has or is close to having some (low) chromatic number. Chapter 2 is the slight exception. We consider an induced version of the classical Turán problem. Introduced by Loh, Tait, Timmons, and Zhou, the induced Turán number ex(n, {H, F-ind}) is the greatest number of edges in an n-vertex graph with no copy of H and no induced copy of F. We asymptotically determine ex(n, {H, F-ind}) for H not bipartite and F neither an independent set nor a complete bipartite graph. We also improve the upper bound for ex(n, {H, K_{2, t}-ind}) as well as the lower bound for the clique number of graphs that have some fixed edge density and no induced K_{2, t}. The next three chapters form the heart of the thesis. Chapters 3 and 4 consider the Erdős-Simonovits question for locally r-colourable graphs: what are the structure and chromatic number of graphs with large minimum degree and where every neighbourhood is r-colourable? Chapter 3 deals with the locally bipartite case and Chapter 4 with the general case. While the subject of Chapters 3 and 4 is a natural local to global colouring question, it is also essential for determining the minimum degree stability of H-free graphs, the focus of Chapter 5. Given a graph H of chromatic number r + 1, this asks for the minimum degree that guarantees that an H-free graph is close to r-partite. This is analogous to the classical edge stability of Erdős and Simonovits. We also consider the question for the family of graphs to which H is not homomorphic, showing that it has the same answer. Chapter 6 considers sparse analogues of the results of Chapters 3 to 5 obtaining the thresholds at which the sparse problem degenerates away from the dense one. Finally, Chapter 7 considers a chromatic Ramsey problem first posed by Erdős: what is the greatest chromatic number of a triangle-free graph on $n$ vertices or with m edges? We improve the best known bounds and obtain tight (up to a constant factor) bounds for the list chromatic number, answering a question of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["36dfbb6234b4e07459db08285a5717db","353adac0d1ebdfd65ab16480263c3c87"]},{"key":"dc:title","label":"Title","values":["The Chromatic Structure of Dense Graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Thomason, Andrew"],"dc:creator":["Illingworth, Frederick"],"dc:creator.authoridentifier":["0000000153502379"],"dc:date.issued":["2021-07-01"],"dc:description.abstract":["This thesis focusses on extremal graph theory, the study of how local constraints on a graph affect its macroscopic structure. We primarily consider the chromatic structure: whether a graph has or is close to having some (low) chromatic number. Chapter 2 is the slight exception. We consider an induced version of the classical Turán problem. Introduced by Loh, Tait, Timmons, and Zhou, the induced Turán number ex(n, {H, F-ind}) is the greatest number of edges in an n-vertex graph with no copy of H and no induced copy of F. We asymptotically determine ex(n, {H, F-ind}) for H not bipartite and F neither an independent set nor a complete bipartite graph. We also improve the upper bound for ex(n, {H, K_{2, t}-ind}) as well as the lower bound for the clique number of graphs that have some fixed edge density and no induced K_{2, t}. The next three chapters form the heart of the thesis. Chapters 3 and 4 consider the Erdős-Simonovits question for locally r-colourable graphs: what are the structure and chromatic number of graphs with large minimum degree and where every neighbourhood is r-colourable? Chapter 3 deals with the locally bipartite case and Chapter 4 with the general case. While the subject of Chapters 3 and 4 is a natural local to global colouring question, it is also essential for determining the minimum degree stability of H-free graphs, the focus of Chapter 5. Given a graph H of chromatic number r + 1, this asks for the minimum degree that guarantees that an H-free graph is close to r-partite. This is analogous to the classical edge stability of Erdős and Simonovits. We also consider the question for the family of graphs to which H is not homomorphic, showing that it has the same answer. Chapter 6 considers sparse analogues of the results of Chapters 3 to 5 obtaining the thresholds at which the sparse problem degenerates away from the dense one. Finally, Chapter 7 considers a chromatic Ramsey problem first posed by Erdős: what is the greatest chromatic number of a triangle-free graph on $n$ vertices or with m edges? We improve the best known bounds and obtain tight (up to a constant factor) bounds for the list chromatic number, answering a question of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot."],"dc:format.checksum.md5":["36dfbb6234b4e07459db08285a5717db","353adac0d1ebdfd65ab16480263c3c87"],"dc:identifier.doi":["10.17863/CAM.77660"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/7f205e4f-b3f6-4159-9a08-30b13e8a09f2/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/330218"],"dc:rights":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/9cbd783e-4e0a-404f-ba8f-774f94437bfe/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["Extremal Graph Theory","Combinatorics","Ramsey Theory","Graph Colouring","Stability","Dense Graphs"],"dc:title":["The Chromatic Structure of Dense Graphs"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:07Z"}