The chromatic profile of locally colourable graphs

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 any $n$-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 each $k$, what minimum degree guarantees that a triangle-free graph is $k$-colourable? The 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, Łuczak 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 as well as showing that every $n$-vertex locally $b$-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.

34 pages, 18 figures. Final version. arXiv admin note: text overlap with arXiv:2012.10409

References in corpus (3)

• Coloring dense graphs via VC-dimension
• The chromatic profile of locally colourable graphs
• Minimum degree stability of $H$-free graphs

Cited by in corpus (3)

• The chromatic profile of locally colourable graphs
• Minimum degree stability of $H$-free graphs
• The chromatic profile of locally bipartite graphs