  We introduce the notion of the { \it strong $(r,p)$ cover} number
$\chi^c(G,k,r,p)$ for $k$-uniform hypergraphs $G(V,E)$, where $\chi^c(G,k,r,p)$
denotes the minimum number of $r$-colorings of vertices in $V$ such that each
hyperedge in $E$ contains at least $min(p,k)$ vertices of distinct colors in at
least one of the $\chi^c(G,k,r,p)$ $r$-colorings. We derive the exact values of
$\chi^c(K_n^k,k,r,p)$ for small values of $n$, $k$, $r$ and $p$, where $K_n^k$
denotes the complete $k$-uniform hypergraph of $n$ vertices. We study the
variation of $\chi^c(G,k,r,p)$ with respect to changes in $k$, $r$, $p$ and
$n$; we show that $\chi^c(G,k,r,p)$ is at least (i) $\chi^c(G,k,r-1,p-1)$, and,
(ii) $\chi^c(G',k-1,r,p-1)$, where $G'$ is any $(n-1)$-vertex induced
sub-hypergraph of $G$. We establish a general upper bound for
$\chi^c(K_n^k,k,r,p)$ for complete $k$-uniform hypergraphs using a
divide-and-conquer strategy for arbitrary values of $k$, $r$ and $p$. We also
relate $\chi^c(G,k,r,p)$ to the number $|E|$ of hyperedges, and the maximum
{\it hyperedge degree (dependency)} $d(G)$, as follows. We show that
$\chi^c(G,k,r,p)\leq x$ for integer $x>0$, if $|E|\leq
\frac{1}{2}({\frac{r^k}{(t-1)^k \binom{r}{t-1}}})^x $, for any $k$-uniform
hypergraph. We prove that a { \it strong $(r,p)$ cover} of size $x$ can be
computed in randomized polynomial time if $d(G)\leq
\frac{1}{e}({\frac{r^k}{(p-1)^k \binom{r}{p-1}}})^x-1$.
