Colouring random graphs (Q2822597)

This chapter concerns coloring of random graphs and basically answers the following two questions. Suppose that \(m\sim cn\) for some \(c\geq1/2\). Is there a positive integer function \(f=f(n)\) for which \(\chi(G_{n,m})=f\) a.a.s., and if so how large is it? What is the a.a.s. first-order approximate behavior of the chromatic number of a uniformly chosen graph with vertex-set \([n]\)? Related topics covered in this chapter include the greedy algorithm, the stability number, concentration results, the coloring rate and anti-concentration, \(k\)-colorability, etc. In addition to the classical random graph models of Erdős and Rényi, several variants including random regular graphs, random geometric graphs, and random graph models related to the coloring of planar graphs, are discussed. Some results on specific chromatic parameters such as edge and total colorings are also discussed for the dense Erdős-Rényi random graphs amongst others.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].