On the effect of randomness on planted 3-coloring models

Roee David, Uriel Feige

We present the hosted coloring framework for studying algorithmic and hardness results for the $k$-coloring problem. There is a class $\mathcal{H}$ of host graphs. One selects a graph…