Finding biclique partitions of co-chordal graphs

DOI10.1016/J.DAM.2023.05.001MaRDI QIDQ6162046zbMATH OpenFDO

Authors Bochuan Lyu, Illya V. Hicks

Publication date 15 June 2023

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

Full work available at URL https://arxiv.org/abs/2203.02837

zbMATH Keywords

split graphsbiclique partitionsco-chordal graphsclique vertex irreducible

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Abstract: The biclique partition number $(extbp)$ of a graph $G$ is referred to as the least number of complete bipartite (biclique) subgraphs that are required to cover the edges of the graph exactly once. In this paper, we show that the biclique partition number ($extbp$) of a co-chordal (complementary graph of chordal) graph $G=(V,E)$ is less than the number of maximal cliques ($extmc$) of its complementary graph: a chordal graph $G^c=(V,E^c)$. We first provide a general framework of the ``divide and conquer" heuristic of finding minimum biclique partitions of co-chordal graphs based on clique trees. Furthermore, a heuristic of complexity $O[|V|(|V|+|E^c|)]$ is proposed by applying lexicographic breadth-first search to find structures called moplexes. Either heuristic gives us a biclique partition of $G$ with size $extmc(G^c)-1$. In addition, we prove that both of our heuristics can solve the minimum biclique partition problem on $G$ exactly if its complement $G^c$ is chordal and clique vertex irreducible. We also show that $extmc(G^c)-2leqextbp(G)leqextmc(G^c)-1$ if $G$ is a split graph.

Recommendations

• Computation of the biclique partition number for graphs with specific blocks
• scientific article; zbMATH DE number 5543290
• The biclique partitioning polytope
• The biclique partition number of some important graphs
• Regarding two conjectures on clique and biclique partitions

Cites work

• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• scientific article; zbMATH DE number 970791 (Why is no real title available?)
• A counting proof of the Graham-Pollak theorem
• A new proof of a theorem of Graham and Pollak
• Algorithmic Aspects of Vertex Elimination on Graphs
• Biclique covers and partitions
• Biclique graphs of split graphs
• Clique irreducibility and clique vertex irreducibility of graphs
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• Graph-Theoretic Concepts in Computer Science
• Improved bounds for the Graham-Pollak problem for hypergraphs
• Incidence matrices and interval graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Moplex orderings generated by the LexDFs algorithm
• On the Addressing Problem for Loop Switching
• On the decomposition ofkn into complete bipartite graphs
• Ordered biclique partitions and communication complexity problems
• Proofs from THE BOOK. Including illustrations by Karl H. Hofmann
• Regarding two conjectures on clique and biclique partitions
• Separability generalizes Dirac's theorem
• Some improved bounds on communication complexity via new decomposition of cliques
• The biclique partition number of some important graphs
• The biclique partitioning polytope
• Variations on a theme of Graham and Pollak

Cited in

(4)

• On bicliques, biclique partitions and related classes of cographs
• Computation of the biclique partition number for graphs with specific blocks
• Coherent network partitions: characterizations with cographs and prime graphs
• On co-bicliques

This page was built for publication: Finding biclique partitions of co-chordal graphs

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