On hereditary Helly classes of graphs

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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.71--78
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00972306
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:07:43
Dernière modification le : mercredi 22 août 2018 - 12:12:01
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:30:33

Fichier

744-3182-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00972306, version 1

Collections

Citation

Marina Groshaus, Jayme Luiz Szwarcfiter. On hereditary Helly classes of graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.71--78. 〈hal-00972306〉

Partager

Métriques

Consultations de la notice

325

Téléchargements de fichiers

249