UCL Discovery Stage
UCL home » Library Services » Electronic resources » UCL Discovery Stage

The chromatic profile of locally colourable graphs

Illingworth, Freddie; (2022) The chromatic profile of locally colourable graphs. Combinatorics, Probability and Computing , 31 (6) pp. 976-1009. 10.1017/S0963548322000050. Green open access

[thumbnail of loc_col_CPC.pdf]
Preview
Text
loc_col_CPC.pdf - Published Version

Download (1MB) | Preview

Abstract

The classical Andrásfai-Erdős-Sós theorem considers the chromatic number of$K_{r + 1}$-free graphs with large minimum degree, and in the case,$r = 2$says that anyn-vertex triangle-free graph with minimum degree greater than$2/5 \cdot n$is bipartite. This began the study of the chromatic profile of triangle-free graphs: for eachk, what minimum degree guarantees that a triangle-free graph isk-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 isb-colourable (locallyb-partite graphs) as well as the family where the common neighbourhood of everya-clique isb-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 everyn-vertex locallyb-partite graph with minimum degree greater than$(1 - 1/(b + 1/7)) \cdot n$is$(b + 1)$-colourable. Understanding these locally colourable graphs is crucial for extending the Andrásfai-Erdős-Sós theorem to non-complete graphs, which we develop elsewhere.

Type: Article
Title: The chromatic profile of locally colourable graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1017/S0963548322000050
Publisher version: http://dx.doi.org/10.1017/s0963548322000050
Language: English
Additional information: Creative Common License - CCCreative Common License - BY This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited. Copyright © The Author(s), 2022. Published by Cambridge University Press
Keywords: Science & Technology, Technology, Physical Sciences, Computer Science, Theory & Methods, Mathematics, Statistics & Probability, Computer Science, Locally Colourable Graphs, Chromatic Profile
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery-pp.ucl.ac.uk/id/eprint/10189637
Downloads since deposit
84Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item