2023/02/24 by Lyu, Bochuan, Hicks, Illya V.
#05C70 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2302.12775
The biclique cover number (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 bc(G) ≥ \lceil log2(mc(Gc)) \rceil ≥ \lceil log2(χ(G)) \rceil for an arbitrary graph G, where χ(G) is the chromatic number of G and mc(Gc) is the number of maximal cliques of the complementary graph Gc, i.e., the number of maximal independent sets of G. We also show that \lceil log2(mc(Gc)) \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 bc(G) with respect to the biclique partition number (bp) of G: bc(G) ≥ \lceil log2(bp(G) + 1) \rceil or bp(G) ≤ 2bc(G) - 1 if G is co-chordal. Furthermore, we show that bc(G) ≤ χr'(T_Kc), where G is a co-chordal graph such that each vertex is in at most two maximal independent sets and χr'(T_Kc) is the optimal edge-ranking number of a clique tree of Gc.