Connection between random graph colorability phase transition and computational complexity!

Planted coloring and stochastic block model, Stochastic block model

Connections between Chromatic number, and a number called graph independence, I think (see pic from lecture).