Let $G(n, d/n)$ be an Erdos-Renyi graph with edge probablity $p = d/n$. For any fixed $k$ sufficiently large, it is known that $d_{k-col} \sim 2 k\log k$ is the sharp threshold for $G(n, d/n)$ to be $k$-colorable. That is, $G(n, d/n)$ is $k$-colorable with high probability if $d < d_{k-col}$ and not $k$-colorable with high probability if $d > d_{k-col}$.

However, if $G(n, d/n)$ is indeed $k$-colorable, it is not clear if it can be colored in polynomial time. I was wondering what is the best known polynomial algorithm to color a random graph.

In addition, are their any hardness result about determining whether $G(n, d/n)$ is $k$-colorable in polynomial time? Will the threshold be different from $d_{k-col}$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.