Phase Transitions in k-Colorability of Random Graphs

We use the first- and second-moment probabilistic and the Potts spin-glass model to find improved upper and lower bounds on the critical average degree d_k governing k-colorability of random large graphs, and found numerical results regarding upper and lower bounds, d_k^+ and d_k^- respectively, such that for large k, d_k^- = d_k^+ -1. Moreover, it seems that d_k^+ and d_k^- differ from the naive upper bound, 2 ln k / (\ln k - \ln (k-1)), by some small constant.