  We present the hosted coloring framework for studying algorithmic and
hardness results for the $k$-coloring problem. There is a class ${\cal H}$ of
host graphs. One selects a graph $H\in{\cal H}$ and plants in it a balanced
$k$-coloring (by partitioning the vertex set into $k$ roughly equal parts, and
removing all edges within each part). The resulting graph $G$ is given as input
to a polynomial time algorithm that needs to $k$-color $G$ (any legal
$k$-coloring would do -- the algorithm is not required to recover the planted
$k$-coloring). Earlier planted models correspond to the case that ${\cal H}$ is
the class of all $n$-vertex $d$-regular graphs, a member $H\in{\cal H}$ is
chosen at random, and then a balanced $k$-coloring is planted at random. Blum
and Spencer [1995] designed algorithms for this model when $d=n^{\delta}$ (for
$0<\delta\le1$), and Alon and Kahale [1997] managed to do so even when $d$ is a
sufficiently large constant.
  The new aspect in our framework is that it need not involve randomness. In
one model within the framework (with $k=3$) $H$ is a $d$ regular spectral
expander (meaning that except for the largest eigenvalue of its adjacency
matrix, every other eigenvalue has absolute value much smaller than $d$) chosen
by an adversary, and the planted 3-coloring is random. We show that the
3-coloring algorithm of Alon and Kahale [1997] can be modified to apply to this
case. In another model $H$ is a random $d$-regular graph but the planted
balanced $3$-coloring is chosen by an adversary, after seeing $H$. We show that
for a certain range of average degrees somewhat below $\sqrt{n}$, finding a
3-coloring is NP-hard. Together these results (and other results that we have)
help clarify which aspects of randomness in the planted coloring model are the
key to successful 3-coloring algorithms.
