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

The chromatic profile of locally bipartite graphs

Illingworth, Freddie; (2022) The chromatic profile of locally bipartite graphs. Journal of Combinatorial Theory, Series B , 156 pp. 343-388. 10.1016/j.jctb.2022.05.006. Green open access

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

Download (730kB) | Preview

Abstract

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.

Type: Article
Title: The chromatic profile of locally bipartite graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.jctb.2022.05.006
Publisher version: http://dx.doi.org/10.1016/j.jctb.2022.05.006
Language: English
Additional information: © 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords: Science & Technology, Physical Sciences, Mathematics, Graph colouring, Extremal graph theory, TRIANGLE-FREE GRAPHS
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/10189638
Downloads since deposit
88Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item