Complete k-partite graph covers all K_k of a graph Suppose that we have a complete graph $G$ of $n$ vertices. What is the minimum number of complete $k$-partite graph (subgraph of $G$) that covers all the complete graph of $k$ vertices of $V(G)$? Are there any results related to this problem? Any lower bounds or upper bounds?
To phrase it in another way. Suppose that there are $n$ students entering in an exam of some multiple choice questions, each has $k$ choices. After the exam, you find that among any $k$ students, there is (at least) a question such that these $k$ students answer differently. Then what is the minimum number of questions in this exam?
For example, when $k=2$, it is asking how many bipartite graph is need to cover a complete graph.
 A: For every graph $G$, the smallest number of complete bipartite subgraphs needed to cover the edges of $G$ is called the biclique covering number, and is denoted by $bc(G)$.  The corresponding partitioning problem is called the biclique partitioning number, and is denoted by $bp(G)$.  Both these problems have been widely studied, not just for complete graphs.  
For complete graphs, it is a classical result of Graham and Pollak that $bp(K_n)=n-1$.  On the other hand, it is easy to show (and this addresses your question), that $bc(K_n) \leq \log(n)$.  Thus, $bp(G)$ and $bc(G)$ can be exponentially far apart.  
For a slew of results for $bp(G)$ and $bc(G)$ for other classes of graphs, see the introduction of this paper by Jukna and Kulikov.  
A: A graph $G$ can be covered by $l$ $k$-partite subgraphs if and only if $\chi(G) \leq k^l$.  This is easy to see by thinking of the colours as the elements of $[k]^l$.
Note that, in contrast to the situation described in Tony Huynh's answer, the $k$-partite subgraphs are not required to be complete (but it makes no difference if $G = K_n$).
