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.
展开▼
