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) \geq \lceil \log_2(\text{ mc}(G^c)) \rceil \geq \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) \geq \lceil \log_2(\text{ bp}(G) + 1) \rceil$ or $\text{ bp}(G) \leq 2^{ \text{ bc}(G)} - 1$ if $G$ is co-chordal. Furthermore, we show that $\text{ bc}(G) \leq \chi_r'(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'({ T}_{ { K}^c})$ is the optimal edge-ranking number of a clique tree of $G^c$.
Categories: math.CO cs.DM