  We study the computational complexity of two related problems: recovering a
planted $q$-coloring in $G(n,1/2)$, and finding efficiently verifiable
witnesses of non-$q$-colorability (a.k.a. refutations) in $G(n,1/2)$. Our main
results show hardness for both these problems in a restricted-but-powerful
class of algorithms based on computing low-degree polynomials in the inputs.
  The problem of recovering a planted $q$-coloring is equivalent to recovering
$q$ disjoint planted cliques that cover all the vertices -- a potentially
easier variant of the well-studied planted clique problem. Our first result
shows that this variant is as hard as the original planted clique problem in
the low-degree polynomial model of computation: each clique needs to have size
$k \gg \sqrt{n}$ for efficient recovery to be possible. For the related variant
where the cliques cover a $(1-\epsilon)$-fraction of the vertices, we also show
hardness by reduction from planted clique.
  Our second result shows that refuting $q$-colorability of $G(n,1/2)$ is hard
in the low-degree polynomial model when $q \gg n^{2/3}$ but easy when $q
\lesssim n^{1/2}$, and we leave closing this gap for future work. Our proof is
more subtle than similar results for planted clique and involves constructing a
non-standard distribution over $q$-colorable graphs. We note that while related
to several prior works, this is the first work that explicitly formulates
refutation problems in the low-degree polynomial model.
  The proofs of our main results involve showing low-degree hardness of
hypothesis testing between an appropriately constructed pair of distributions.
For refutation, we show completeness of this approach: in the low-degree model,
the refutation task is precisely as hard as the hardest associated testing
problem, i.e., proving hardness of refutation amounts to finding a "hard"
distribution.
