The chromatic profile of locally bipartite graphs - Illingworth, F (Elsevier, 2022)
In 1973, Erdős and Simonovits asked whether every n-vertex triangle-free graph with minimum degree greater than 1/3 · n is 3-colourable. This question initiated 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. This problem has a rich history which culminated in its complete solution by Brandt and Thomassé. Much less is known about the chromatic profile of H-free graphs for general H. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. Locally bipartite graphs, first mentioned by Łuczak and Thomassé, are the natural variant of triangle-free graphs in which each neighbourhood is bipartite. Here we study the chromatic profile of locally bipartite graphs. We show that every n-vertex locally bipartite graph with minimum degree greater than 4/7 · n is 3-colourable (4/7 is tight) and with minimum degree greater than 6/11 · n is 4-colourable. Although the chromatic profiles of locally bipartite and triangle-free graphs bear some similarities, we will see there are striking differences.