On edge-sets of bicliques in graphs

DOI10.1016/J.DAM.2012.02.004MaRDI QIDQ1759846zbMATH OpenOpenAlexFDO

Authors Marina Groshaus, Pavol Hell, Juraj Stacho

Publication date 22 November 2012

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

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

zbMATH Keywords

intersection graphconformalclique graphbicliqueHelly2-sectionpolynomial time recognition algorithmedge-biclique hypergraphedge-sets of bicliquesintersection structure

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65)

Abstract: A biclique is a maximal induced complete bipartite subgraph of a graph. We investigate the intersection structure of edge-sets of bicliques in a graph. Specifically, we study the associated edge-biclique hypergraph whose hyperedges are precisely the edge-sets of all bicliques. We characterize graphs whose edge-biclique hypergraph is conformal (i.e., it is the clique hypergraph of its 2-section) by means of a single forbidden induced obstruction, the triangular prism. Using this result, we characterize graphs whose edge-biclique hypergraph is Helly and provide a polynomial time recognition algorithm. We further study a hereditary version of this property and show that it also admits polynomial time recognition, and, in fact, is characterized by a finite set of forbidden induced subgraphs. We conclude by describing some interesting properties of the 2-section graph of the edge-biclique hypergraph.

Recommendations

• Biclique-Helly graphs
• Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
• Biclique graphs and biclique matrices
• Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration
• Bicliques in graphs. I: Bounds on their number

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4093512 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 54799 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 2188347 (Why is no real title available?)
• scientific article; zbMATH DE number 2230239 (Why is no real title available?)
• Biclique graphs and biclique matrices
• Biclique-Helly graphs
• Characterizations of derived graphs
• Edge clique graphs and some classes of chordal graphs
• Edge-clique graphs
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• On hereditary Helly classes of graphs
• Sur deux propriétés des classes d'ensembles
• The complexity of clique graph recognition
• The edge intersection graphs of paths in a tree

Cited in

(8)

• On some conjectures on biclique graphs
• On the iterated edge-biclique operator
• Parameterized algorithms for edge biclique and related problems
• Hereditary biclique-Helly graphs: recognition and maximal biclique enumeration
• Biclique graphs and biclique matrices
• On bicliques and the second clique graph of suspensions
• On cliques and bicliques
• On the edge‐biclique graph and the iterated edge‐biclique operator

This page was built for publication: On edge-sets of bicliques in graphs

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