Biclique covers and partitions

MaRDI QIDQ405095zbMATH OpenFDO

Authors Trevor Pinto

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.6363, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p19

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

biclique coversbiclique partitionslocal biclique cover numbersubcube intersection graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05)

Abstract: The biclique cover number (resp. biclique partition number) of a graph $G$, $mathrmbc(G$) (resp. $mathrmbp(G)$), is the least number of biclique (complete bipartite) subgraphs that are needed to cover (resp. partition) the edges of $G$. The emph{local biclique cover number} (resp. local biclique partition number) of a graph $G$, $mathrmlbc(G$) (resp. $mathrmlbp(G)$), is the least $r$ such that there is a cover (resp. partition) of the edges of $G$ by bicliques with no vertex in more than $r$ of these bicliques. We show that $mathrmbp(G)$ may be bounded in terms of $mathrmbc(G)$, in particular, $mathrmbp(G)leqfrac12(3^{m}athrmbc(G)-1)$. However, the analogous result does not hold for the local measures. Indeed, in our main result, we show that $mathrmlbp(G)$ can be arbitrarily large, even for graphs with $mathrmlbc(G)=2$. For such graphs, $G$, we try to bound $mathrmlbp(G)$ in terms of additional information about biclique covers of $G$. We both answer and leave open questions related to this. There is a well known link between biclique covers and subcube intersection graphs. We consider the problem of finding the least $r(n)$ for which every graph on $n$ vertices can be represented as a subcube intersection graph in which every subcube has dimension $r$. We reduce this problem to the much studied question of finding the least $d(n)$ such that every graph on $n$ vertices is the intersection graph of subcubes of a $d$-dimensional cube.

Recommendations

• Biclique cover and local clique cover of graphs
• Regarding two conjectures on clique and biclique partitions
• A note on \(d\)-biclique covers
• Covering graphs with few complete bipartite subgraphs
• Publication:3478420

Cites work

• scientific article; zbMATH DE number 3121508 (Why is no real title available?)
• scientific article; zbMATH DE number 3841905 (Why is no real title available?)
• scientific article; zbMATH DE number 3238444 (Why is no real title available?)
• scientific article; zbMATH DE number 970791 (Why is no real title available?)
• A mathematical analysis of human leukocyte antigen serology
• Bipartite Coverings of Graphs
• Bipartite coverings and the chromatic number
• Bipartite dimensions and bipartite degrees of graphs
• Communication Complexity
• Covering a graph by complete bipartite graphs
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Graph Theory and Probability
• On covering graphs by complete bipartite subgraphs
• On set intersection representations of graphs
• On the Addressing Problem for Loop Switching
• On the coverings of graphs
• On the decomposition of graphs into complete bipartite graphs
• On the decomposition ofkn into complete bipartite graphs
• Topics in Intersection Graph Theory
• Turán and Ramsey properties of subcube intersection graphs

Cited in

(15)

• Finding biclique partitions of co-chordal graphs
• Regarding two conjectures on clique and biclique partitions
• Fractional biclique covers and partitions of graphs
• Biclique cover and local clique cover of graphs
• scientific article; zbMATH DE number 1439493 (Why is no real title available?)
• scientific article; zbMATH DE number 4045794 (Why is no real title available?)
• An overview of graph covering and partitioning
• Coherent network partitions
• Erdős-Pyber theorem for hypergraphs and secret sharing
• On the biclique cover of the complete graph
• Random subcube intersection graphs. I: Cliques and covering
• Coherent network partitions: characterizations with cographs and prime graphs
• Edge clique covering sum of graphs
• The biclique covering number of grids
• Three ways to cover a graph

This page was built for publication: Biclique covers and partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405095)