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.

  • $\begingroup$ Isn't it obvious that this number is $\log_2(n)$ for $k=2$? What am I missing? $\endgroup$ – Goldstern Mar 16 '15 at 16:02
  • $\begingroup$ It is obvious. But what about the general $k$, say $k=3$? $\endgroup$ – 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.

  • $\begingroup$ 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$. $\endgroup$ – Yibo Gao Mar 16 '15 at 16:55
  • $\begingroup$ 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. $\endgroup$ – Tony Huynh Mar 16 '15 at 17:08
  • $\begingroup$ 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$. $\endgroup$ – 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$).

  • $\begingroup$ 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. $\endgroup$ – Will Sawin Mar 16 '15 at 17:45
  • $\begingroup$ Yes, it's an exact characterisation of the graphs that can be covered in this way. $\endgroup$ – Ben Barber Mar 16 '15 at 17:48
  • $\begingroup$ Sorry for making it unclear. I change the problem description. $\endgroup$ – Yibo Gao Mar 16 '15 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.