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.

• Isn't it obvious that this number is $\log_2(n)$ for $k=2$? What am I missing? – Goldstern Mar 16 '15 at 16:02
• It is obvious. But what about the general $k$, say $k=3$? – Yibo Gao Mar 16 '15 at 16:55

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.

• The case of $k=2$ is not very interesting for covering of the complete graph. I want to know about the general case of $k$. – Yibo Gao Mar 16 '15 at 16:55
• Off the top of my head, if you encode the vertices as numbers in base $k$, then you can cover with $\log_k(n)$ complete $k$-bipartite subgraphs. Not sure if you can do better. – Tony Huynh Mar 16 '15 at 17:08
• Sorry that I am not making it clear. I want these $k$-partite subgraphs to cover all the complete graphs of $k$ vertices in $G$, but not just cover $G$. – Yibo Gao Mar 16 '15 at 19:19

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$).

• Isn't this lower bound for $l$ also an upper bound, because given a $k^l$-coloring you can find $l$ different maps from the set of vertices to $\{1,\dots,k\}$ such that each edge connects vertices sent to two different numbers by at least one of the maps? This gives you $l$ $k$-partite graphs. So the answer is exactly $\lceil \log_k n \rceil$ graphs. – Will Sawin Mar 16 '15 at 17:45
• Yes, it's an exact characterisation of the graphs that can be covered in this way. – Ben Barber Mar 16 '15 at 17:48
• Sorry for making it unclear. I change the problem description. – Yibo Gao Mar 16 '15 at 19:24