Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00972306
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, April 3, 2014 - 4:07:43 PM
Last modification on : Tuesday, October 19, 2021 - 11:03:55 PM
Long-term archiving on: : Thursday, July 3, 2014 - 4:30:33 PM

File

744-3182-2-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marina Groshaus, Jayme Luiz Szwarcfiter. On hereditary Helly classes of graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, Vol. 10 no. 1 (1), pp.71--78. ⟨10.46298/dmtcs.440⟩. ⟨hal-00972306⟩

Share

Metrics

Record views

216

Files downloads

632