The chromatic profile of a graph

Abstract

Determining the chromatic number of a graph is a difficult but important problem. Hence, it is not surprising that a variety of questions in Graph Theory concern the search for meaningful upper bounds for the chromatic number of certain families of graphs. One type of graph family that received considerable attention is that of H-free graphs, that is, the family of graphs G which do not contain a given graph H as subgraph. By an old result of Erdős the chromatic number of H-free graphs G can be arbitrarily large (when H is not a forest). Erdős and Simonovits then asked what happens if we additionally introduce a minimum degree for G. This initiated the study of the so-called chromatic profile of a graph H, opening up a number of important directions of research where much remains open today. In the talk I will provide all necessary background, talk about relations of the chromatic profile to other important concepts as the chromatic threshold and the homomorphism threshold, and then talk about some recent new bounds we obtained when small odd cycles are forbidden as subgraphs (in joint work with Nóra Frankl, Domenico Mergoni Cecchelli, Olaf Parczyk, Jozef Skokan).

Speaker Intro

Julia Böttcher is a Professor in Mathematics at the London School of Economics and Political Science. Before moving to London, she studied Computer Science at Humboldt Universität Berlin, received her PhD from Technische Universität München, and spent some years as postdoc at the Universidade de São Paulo. She was a recipient of a Fulkerson Prize in 2018 and an invited sectional speaker at the 2022 International Congress of Mathematicians. She is a member of the British Combinatorial Committee and regularly co-organises the London Colloquia in Mathematics.