Maximal Clique and Edge-Ranking Bounds of Biclique Cover Number

Abstract

The biclique cover number $(\text{bc})$ of a graph $G$ denotes the minimum number of complete bipartite (biclique) subgraphs to cover all the edges of the graph. In this paper, we show that $\text{bc}(G)\ge \lceil {\log }_2(\text{mc}(G^c))\rceil \ge \lceil {\log }_2(\chi (G))\rceil$ for an arbitrary graph $G$, where $\chi (G)$ is the chromatic number of $G$ and $\text{mc}(G^c)$ is the number of maximal cliques of the complementary graph $G^c$, i.e., the number of maximal independent sets of $G$. We also show that $\lceil {\log }_2(\text{mc}(G^c))\rceil$ could be a strictly tighter lower bound of the biclique cover number than other existing lower bounds. We can also provide a bound of $\text{bc}(G)$ with respect to the biclique partition number ($\text{bp}$) of $G$: $\text{bc}(G)\ge \lceil {\log }_2(\text{bp}(G)+1)\rceil$ or $\text{bp}(G)\le 2^{\text{bc}(G)}-1$ if $G$ is co-chordal. Furthermore, we show that $\text{bc}(G)\le {\chi }_r^{\prime }(T_{K^c})$, where $G$ is a co-chordal graph such that each vertex is in at most two maximal independent sets and ${\chi }_r^{\prime }(T_{K^c})$ is the optimal edge-ranking number of a clique tree of $G^c$.