Maximal Clique and Edge-Ranking Bounds of Biclique Cover Number

Publication date 24 February 2023

Abstract: The biclique cover number

(e x t b c)

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

e x t b c (G) g e q l c e i l l o g_{2} (e x t m c (G^{c})) c e i l g e q l c e i l l o g_{2} (c h i (G)) c e i l

for an arbitrary graph

G

, where

c h i (G)

is the chromatic number of

G

and

e x t m c (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

l c e i l l o g_{2} (e x t m c (G^{c})) c e i l

could be a strictly tighter lower bound of the biclique cover number than other existing lower bounds. We can also provide a bound of

e x t b c (G)

with respect to the biclique partition number (

e x t b p

) of

G

:

e x t b c (G) g e q l c e i l l o g_{2} (e x t b p (G) + 1) c e i l

or

e x t b p (G) l e q 2^{e x t b c (G)} - 1

if

G

is co-chordal. Furthermore, we show that

e x t b c (G) l e q c h {i_{r}}^{'} (T_{K^{c}})

, where

G

is a co-chordal graph such that each vertex is in at most two maximal independent sets and

c h {i_{r}}^{'} (T_{K^{c}})

is the optimal edge-ranking number of a clique tree of

G^{c}

.

This page was built for publication: Maximal Clique and Edge-Ranking Bounds of Biclique Cover Number