×

zbMATH — the first resource for mathematics

Biclique-Helly graphs. (English) Zbl 1140.05314
Summary: A graph is biclique-Helly when its family of (maximal) bicliques is a Helly family. We describe characterizations for biclique-Helly graphs, leading to polynomial time recognition algorithms. In addition, we relate biclique-Helly graphs to the classes of clique-Helly, disk-Helly and neighborhood-Helly graphs.

MSC:
05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bandelt, H.-J., Farber, M., Hell, P.: Absolute reflexive retracts and absolute bipartite graphs. Discrete Applied Mathematics 44, 9–20 (1993) · Zbl 0795.05133
[2] Bandelt, H.-J., Pesch, E.: Dismantling absolute retracts of reflexive graphs. European J. Combinatorics 10, 211–220 (1989) · Zbl 0674.05065
[3] Bandelt, H.-J., Prisner, E.: Clique graphs and Helly graphs. J. Combin Theory B 51, 34–45 (1991) · Zbl 0726.05060
[4] Berge, C.: Hypergraphs. North Holland Mathematical Library, vol.45, Elsevier Science Publishers B.V., Amsterdam, 1989
[5] Berge, C., Duchet, P.: A generalization of Gilmore’s theorem. In: Fiedler, M. (ed.) Recent Advances in Graph Theory. Acad. Praha, Prague pp 49–55 (1975) · Zbl 0325.05125
[6] Bondy, A., Durán, G., Lin, M., Szwarcfiter, J.: Self-clique graphs and matrix permutations. Journal of Graph Theory 44, 178–192 (2003) · Zbl 1031.05115
[7] Burzyn, P., Bonomo, F., Durán, G.: NP-completeness results for edge modification problems. Discrete Applied Mathematics 154(13), 1824–1844 (2006) · Zbl 1110.68094
[8] Dragan, F.F.: Centers of Graphs and the Helly property. PhD thesis, Moldava State University, Chisinau, Moldava (1989) (In russian)
[9] Escalante, F.: Über iterierte Clique-Graphen. Abhandlungender Mathematischen Seminar der Universität Hamburg 39, 59–68 (1973) · Zbl 0266.05116
[10] Hamelink, B.C.: A partial characterization of clique graphs. J. Combin Theory 5, 192–197 (1968) · Zbl 0167.22203
[11] Pavol Hell, Personal Communication (2003)
[12] Larrión, F., Neumann-Lara, V., Pizaña, M.A., Porter, T.D.: A hierarchy of self-clique graphs. Discrete Mathematics 282, 193–208 (2004) · Zbl 1042.05073
[13] Müller, H.: On edge perfectness and classes of bipartite graphs. Discrete Math. 149, 159–187 (1996) · Zbl 0844.68095
[14] Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131, 651–654 (2003) · Zbl 1026.68068
[15] Prisner, E.: Bicliques in graphs I. Bounds on their number. Combinatorica 20, 109–117 (2000) · Zbl 0980.05033
[16] Prisner, E.: Bicliques in graphs II. Recognizing k-path graphs and underlying graphs of line digraphs. Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1335, 253–287 (1997) · Zbl 0895.68103
[17] Szwarcfiter, J.L.: Recognizing clique-Helly graphs. Ars Combinatoria 45, 29–32 (1997) · Zbl 0933.05127
[18] Tuza, Z.: Covering of graphs by complete bipartite subgraphs: complexity of 0-1 matrices. Combinatorica 4, 111–116 (1984) · Zbl 0559.05050
[19] Robert, F.S., Spencer, J.H.: A characterization of clique graphs. J. Combin. Theory B 10, 102–108 (1971) · Zbl 0215.05801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.