Current browse context:
math.CO
Change to browse by:
References & Citations
Mathematics > Combinatorics
Title: Maximal Clique and Edge-Ranking Bounds of Biclique Cover Number
(Submitted on 24 Feb 2023 (v1), last revised 9 Mar 2023 (this version, v2))
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) \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$.
Submission history
From: Bochuan Lyu [view email][v1] Fri, 24 Feb 2023 17:43:49 GMT (60kb)
[v2] Thu, 9 Mar 2023 15:37:41 GMT (42kb)
Link back to: arXiv, form interface, contact.