3
$\begingroup$

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.

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

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Mar 16, 2015 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
    Commented Mar 16, 2015 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
    Commented Mar 16, 2015 at 19:19
3
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .