The freezing threshold for k-colourings of a random graph
The freezing threshold for k-colourings of a random graph
We rigorously determine the exact freezing threshold, rkf, for k-colourings of a random graph. We prove that for random graphs with density above rkf, almost every colouring is such that a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations whereby …