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
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


Files produced by the author(s)




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⟩



Record views


Files downloads