The chromatic profile of locally colourable graphs

Journal article

The classical Andrásfai-Erd˝os-Sós theorem considers the chromatic number of Kr+1-free graphs with large minimum degree, and in the case, r = 2 says that any n-vertex triangle-free graph with minimum degree greater than 2/5 · n is bipartite. This began the study of the chromatic profile of triangle-free graphs: for each k, what minimum degree guarantees that a triangle-free graph is k-colourable? The chromatic profile has been extensively studied and was finally determined by Brandt and Thomassé. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. As a natural variant, Luczak and Thomassé introduced the notion of a locally bipartite graph in which each neighbourhood is 2-colourable. Here we study the chromatic profile of the family of graphs in which every neighbourhood is b-colourable (locally b-partite graphs) as well as the family where the common neighbourhood of every a-clique is b-colourable. Our results include the chromatic thresholds of these families (extending a result of Allen, Böttcher, Griffiths, Kohayakawa and Morris) as well as showing that every n-vertex locally b-partite graph with minimum degree greater than (1 − 1/(b + 1/7)) · n is (b + 1)-colourable. Understanding these locally colourable graphs is crucial for extending the Andrásfai-Erd˝os-Sós theorem to non-complete graphs, which we develop elsewhere.

Authors: Illingworth, F

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Combinatorics, Probability and Computing
• Volume: 31
• Issue: 6
• Pages: 976-1009
• Publication date: 2022-05-10
• Acceptance date: 2022-04-04
• DOI: 10.1017/S0963548322000050
• EISSN: 1469-2163
• ISSN: 0963-5483
• Language: English
• Keywords: chromatic profile; FFR; locally colourable graphs