Colouring random graphs

The main objects of my talk are graphs, which consist of a finite set of vertices and a set of edges—pairwise connections between the vertices. A fundamental and well-studied parameter in graph theory and theoretical computer science is the chromatic number, the minimum number of colors required to color the vertices so that adjacent vertices always have different colors.

Understanding the chromatic number when the underlying graph is random (for example, chosen uniformly at random from all graphs with a given number of vertices) has been a central problem since the inception of random graph theory in the 1960s, yet many fundamental questions remain open. In this talk, I will discuss significant recent progress on this topic and highlight several promising directions for future research. The results presented are drawn from multiple papers, most recently in collaboration with A. Heckel.