  The problems of computing graph colorings and clique covers are central
challenges in combinatorial optimization. Both of these are known to be
NP-hard, and thus computationally intractable in the worst-case instance. A
prominent approach for computing approximate solutions to these problems is the
celebrated Lov\'asz theta function $\vartheta(G)$, which is specified as the
solution of a semidefinite program (SDP), and hence tractable to compute. In
this work, we move beyond the worst-case analysis and set out to understand
whether the Lov\'asz theta function recovers clique covers for random instances
that have a latent clique cover structure, possibly obscured by noise. We
answer this question in the affirmative and show that for graphs generated from
the planted clique model we introduce in this work, the SDP formulation of
$\vartheta(G)$ has a unique solution that reveals the underlying clique-cover
structure with high-probability. The main technical step is an intermediate
result where we prove a deterministic condition of recovery based on an
appropriate notion of sparsity.
