The chromatic profile of locally bipartite graphs
<p>In 1973, Erdős and Simonovits asked whether every <i>n</i>-vertex triangle-free graph with minimum degree greater than 1/3 · <i>n</i> is 3-colourable. This question initiated the study of the chromatic profile of triangle-free graphs: for each <i>k</i>, w...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2022
|
| Summary: | <p>In 1973, Erdős and Simonovits asked whether every <i>n</i>-vertex triangle-free graph with minimum degree greater than 1/3 · <i>n</i> is 3-colourable. This question initiated the study of the chromatic profile of triangle-free graphs: for each <i>k</i>, what minimum degree guarantees that a triangle-free graph is <i>k</i>-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 <i>H</i>-free graphs for general <i>H</i>.</p>
<br>
<p>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 <i>n</i>-vertex locally bipartite graph with minimum degree greater than 4/7 · <i>n</i> is 3-colourable (4/7 is tight) and with minimum degree greater than 6/11 · <i>n</i> is 4-colourable. Although the chromatic profiles of locally bipartite and triangle-free graphs bear some similarities, we will see there are striking differences.</p> |
|---|