On covering graphs by complete bipartite subgraphs

DOI10.1016/j.disc.2008.09.036zbMath1218.05136OpenAlexW2152486369MaRDI QIDQ1025967

Alexander S. Kulikov, Stasys P. Jukna

Publication date: 23 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.09.036

zbMATH Keywords

Boolean functionscommunication complexitybicliquefractional coversedge clique covering number

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (14)

Regarding two conjectures on clique and biclique partitions ⋮ An overview of graph covering and partitioning ⋮ Some improved bounds on communication complexity via new decomposition of cliques ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Biclique covers and partitions ⋮ Mod/Resc parsimony inference: theory and application ⋮ Biclique cover and local clique cover of graphs ⋮ Turán and Ramsey Properties of Subcube Intersection Graphs ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ On set intersection representations of graphs ⋮ Efficient approximation for restricted biclique cover problems ⋮ Ordered biclique partitions and communication complexity problems ⋮ Fooling-sets and rank

Cites Work

• Unnamed Item
• Unnamed Item
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Covering graphs by the minimum number of equivalence relations
• On the coverings of graphs
• On the ratio of optimal integral and fractional covers
• Graph complexity and slice functions
• Problems and results in extremal combinatorics. I.
• On the fractional intersection number of a graph
• Some structural properties of low-rank matrices related to computational complexity
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Applications of matrix methods to the theory of lower bounds in computational complexity
• On Graph Complexity
• On set intersection representations of graphs
• Bipartite Coverings of Graphs
• The Shrinkage Exponent of de Morgan Formulas is 2
• Fractional Covers and Communication Complexity
• On the Addressing Problem for Loop Switching

This page was built for publication: On covering graphs by complete bipartite subgraphs