Colouring random graphs

© Cambridge University Press 2015. Typically how many colours are required to colour a graph? In other words, given a graph chosen randomly, what can we expect its chromatic number to be? We survey the classic interpretation of this question, with the binomial or Erdős–Rényi random graph and the usual chromatic number. We also treat a few variations, not only of the random graph model, but also of the chromatic parameter. Introduction How many colours are typically necessary to colour a graph? We survey a number of perspectives on this natural question, which is central to random graph theory and to probabilistic and extremal combinatorics. It has stimulated a vibrant area of research, with a rich history extending back through more than half a century. Erdős and Rényi [36] asked a form of this question in a celebrated early paper on random graphs in 1960. Let Gn, m be a graph chosen uniformly at random from the set of graphs with vertex-set [n] = {1, 2, …, n} and m edges. In this probabilistic model, we cannot rule out the possibility that Gn, m is, for example, the disjoint union of one large clique and some isolated vertices, or perhaps one Turán graph (a balanced complete multipartite graph) and some isolated vertices. The resulting range is large: in the former situation the chromatic number could be about, while in the latter it could be 2 if m ≤ n2/4. These outcomes are unlikely, however, and we are interested in the most probable ones. To state the question properly, we say that an event An (which here always describes a property of a random graph on the vertex-set [n]) holds asymptotically almost surely (a.a.s.) if the probability that An holds satisfies ℙ(An) → 1 as n → ∞. Erdős and Rényi asked the following question.