Maximal Clique and Edge-Ranking Bounds of Biclique Cover Number

The biclique cover number $(\text{bc})$ of a graph $G$ is referred to as the least number of complete bipartite (biclique) subgraphs that are required to cover all the edges of the graph. In this paper, we show that the biclique cover number $(\text{bc})$ of a graph $G$ is no less than $\lceil \log_2(\text{mc}(G^c)) \rceil$, where $\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 $\text{bc}(G) \leq \chi_r'(\mathcal{T}_{\mathcal{K}^c})$ where $G$ is a co-chordal graph such that each vertex is in at most two maximal independent sets and $\chi_r'(\mathcal{T}_{\mathcal{K}^c})$ is the optimal edge-ranking number of a clique tree of $G^c$. By identifying the new lower and upper bounds of $\text{bc}(G)$, we prove that $\text{bc}(G) = \lceil \log_2(\text{mc}(G^c)) \rceil$ if $G^c$ is a path or windmill graph.