2026-09-23T02:02:28Zhttps://api.repository.cam.ac.uk/server/oai/request

oai:www.repository.cam.ac.uk:1810/3302182023-12-22T13:01:59Zcom_1810_213747com_1810_256064col_1810_213748

The Chromatic Structure of Dense Graphs 10.17863/CAM.77660 Illingworth, Frederick 0000000153502379 Thomason, Andrew 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. University of Cambridge 2021-07-01 Thesis Doctoral Doctor of Philosophy (PhD) eng https://www.repository.cam.ac.uk/handle/1810/330218 https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/7f205e4f-b3f6-4159-9a08-30b13e8a09f2/download 36dfbb6234b4e07459db08285a5717db https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/9cbd783e-4e0a-404f-ba8f-774f94437bfe/download 353adac0d1ebdfd65ab16480263c3c87 https://www.rioxx.net/licenses/all-rights-reserved/ Extremal Graph Theory Combinatorics Ramsey Theory Graph Colouring Stability Dense Graphs