Finding biclique partitions of co-chordal graphs

DOI10.1016/J.DAM.2023.05.001zbMATH Open1516.05188arXiv2203.02837MaRDI QIDQ6162046FDOQ6162046

Authors: Bochuan Lyu, Illya V. Hicks 

Publication date: 15 June 2023

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

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.

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

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

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)

Cites Work

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

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)