Artículo
Groshaus, M.; Szwarcfiter, J.L. "On hereditary Helly classes of graphs" (2008) Discrete Mathematics and Theoretical Computer Science. 10(1):71-78
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
In graph theory, the Helly property has been applied to families of sets, such as cliques, disks, bicliques, and neighbourhoods, leading to the classes of clique-Helly, disk-Helly, biclique-Helly, neighbourhood-Helly graphs, respectively. A natural question is to determine for which graphs the corresponding Helly property holds, for every induced subgraph. This leads to the corresponding classes of hereditary clique-Helly, hereditary disk-Helly, hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. In this paper, we describe characterizations in terms of families of forbidden subgraphs, for the classes of hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. We consider both open and closed neighbourhoods. The forbidden subgraphs are all of fixed size, implying polynomial time recognition for these classes. © 2008 Discrete Mathematics and Theoretical Computer Science (DMTCS).
Registro:
| Documento: | Artículo |
| Título: | On hereditary Helly classes of graphs |
| Autor: | Groshaus, M.; Szwarcfiter, J.L. |
| Filiación: | Universidad de Buenos Aires, Fac. de Ciencias Exactas y Naturales, Dep. de Computatión Universidade Federal do Rio, de Janeiro Instituto de Matemática, NCE and COPPE |
| Idioma: | Inglés |
| Palabras clave: | Algorithms; Bicliques; Graph classes; Helly property; (e ,2e) theory; (SPM) classes; Applied (CO); Biclique; Discrete Mathematics; Forbidden subgraphs; Induced subgraph; Neighbourhood; OF graphs; Polynomial-time; Property (S); Computer science; Disks (structural components); Polynomial approximation; Topology; Graph theory |
| Año: | 2008 |
| Volumen: | 10 |
| Número: | 1 |
| Página de inicio: | 71 |
| Página de fin: | 78 |
| Título revista: | Discrete Mathematics and Theoretical Computer Science |
| Título revista abreviado: | Discrete Math. Theor. Comput. Sci. |
| ISSN: | 14627264 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v10_n1_p71_Groshaus |
Referencias:
- Bandelt, H.-J., Chepoi, V., Metric graph theory and geometry: A survey (2006) Contemporary Mathematics, Proceedings of the Joint Summer Research Conference on Discrete and Computational Geometry, , J. E. Goodman, J. Pach and R. Pollack, eds, to appear
- Bandelt, H.-J., Farber, M., Hell, P., Absolute reflexive retracts and absolute bipartite graphs (1993) Discrete Applied Mathematics, 44, pp. 9-20
- Bandelt, H.-J., Prisner, E., Clique graphs and Helly graphs (1991) Journal of Combinatorial Theory B, 51, pp. 34-45
- Bandelt, H.-J., Pesch, E., Dismantling absolute retracts of reflexive graphs (1989) European Journal of Combinatorics, 10, pp. 211-220
- Berge, C., Hypergraphs (1989) North Holland Mathematical Library, 45. , Elsevier Science Publishers B.V, Amsterdam
- Bondy, A., Durán, G., Lin, M., Szwarcfiter, J.L., Self-clique graphs and matrix permutations (2003) Journal of Graph Theory, 44, pp. 178-192
- Brandstädt, A., Le, V., Spinrad, J., Graph Classes. A survey (1999) SIAM Monographs on Discrete Mathematics and Applications
- Burzyn, P., Bonomo, F., Durán, G., NP-completeness results for edge modification problems (2006) Discrete Applied Mathematics, 154, pp. 1824-1844
- Dragan, F.F., Centers of Graphs and the Helly property (1989), PhD thesis, Moldova State University, Chisinau, Moldova, In russianEscalante, F., Über iterierte Clique-Graphen (1973) Abhändlungen der Mathernatischen Seminar der Uni-versität Hamburg, 39, pp. 59-68
- Groshaus, M., Szwarcfiter, J.L., Biclique-Helly graphs Graphs and Combinatorics, , to appear. DOI 10.1007/s00373-007-0756-6
- Hamelink, B.C., A partial characterization of clique graphs (1968) Journal of Combinatorial Theory, 5, pp. 192-197
- Hell, P., (2003), Personal CommunicationLarrión, F., Neumann-Lara, V., Pizaña, M.A., Porter, T.D., A hierarchy of self-clique graphs (2004) Discrete Mathematics, 282, pp. 193-208
- Müller, H., On edge perfectness and classes of bipartite graphs (1996) Discrete Mathematics, 149, pp. 159-187
- Peeters, R., The maximum edge biclique problem is NP-complete (2003) Discrete Applied Mathematics, 131, pp. 651-654
- Prisner, E., Bicliques in graphs, I: Bounds on their number (2000) Combinatorica, 20, pp. 109-117
- Prisner, E., Hereditary clique-Helly graphs (1993) Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 216-220
- Roberts, F.S., Spencer, J.H., A characterization of clique graphs (1971) Journal of Combinatorial Theory B, 10, pp. 102-108
- Tuza, Z., Covering of graphs by complete bipartite subgraphs: Complexity of 0-1 matrices (1984) Combinatorica, 4, pp. 111-116
Citas:
---------- APA ----------
Groshaus, M. & Szwarcfiter, J.L. (2008) . On hereditary Helly classes of graphs. Discrete Mathematics and Theoretical Computer Science, 10(1), 71-78.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v10_n1_p71_Groshaus [ ]
---------- CHICAGO ----------
Groshaus, M., Szwarcfiter, J.L. "On hereditary Helly classes of graphs" . Discrete Mathematics and Theoretical Computer Science 10, no. 1 (2008) : 71-78.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v10_n1_p71_Groshaus [ ]
---------- MLA ----------
Groshaus, M., Szwarcfiter, J.L. "On hereditary Helly classes of graphs" . Discrete Mathematics and Theoretical Computer Science, vol. 10, no. 1, 2008, pp. 71-78.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v10_n1_p71_Groshaus [ ]
---------- VANCOUVER ----------
Groshaus, M., Szwarcfiter, J.L. On hereditary Helly classes of graphs. Discrete Math. Theor. Comput. Sci. 2008;10(1):71-78.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v10_n1_p71_Groshaus [ ]
