Biclique covers and partitions

Trevor Pinto¹

¹Queen Mary University of London

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

The biclique cover number (resp. biclique partition number) of a graph $G$, $\mathrm{bc}(G$) (resp. $\mathrm{bp}(G)$), is the least number of bicliques - complete bipartite subgraphs - that are needed to cover (resp. partition) the edges of $G$.The local biclique cover number (resp. local biclique partition number) of a graph $G$, $\mathrm{lbc}(G$) (resp. $\mathrm{lbp}(G)$), is the least $r$ such that there is a cover (resp. partition) of the edges of $G$ by bicliques with no vertex in more than $r$ of these bicliques.We show that $\mathrm{bp}(G)$ may be bounded in terms of $\mathrm{bc}(G)$, in particular, $\mathrm{bp}(G)\leq \frac{1}{2}(3^\mathrm{bc(G)}-1)$. However, the analogous result does not hold for the local measures. Indeed, in our main result, we show that $\mathrm{lbp}(G)$ can be arbitrarily large, even for graphs with $\mathrm{lbc}(G)=2$. For such graphs, $G$, we try to bound $\mathrm{lbp}(G)$ in terms of additional information about biclique covers of $G$. We both answer and leave open questions related to this.There is a well known link between biclique covers and subcube intersection graphs. We consider the problem of finding the least $r(n)$ for which every graph on $n$ vertices can be represented as a subcube intersection graph in which every subcube has dimension $r$. We reduce this problem to the much studied question of finding the least $d(n)$ such that every graph on $n$ vertices is the intersection graph of subcubes of a $d$-dimensional cube.

Détail

DOI : 10.37236/3595

Classification : 05C70, 05C60, 05D05
Mots-clés : biclique covers, biclique partitions, local biclique cover number, subcube intersection graphs