%0 Journal Article
%T On Hereditary Helly classes of graphs
%A Marina Groshaus
%A Jayme Luiz Szwarcfiter
%J Discrete Mathematics & Theoretical Computer Science
%D 2008
%I Discrete Mathematics & Theoretical Computer Science
%X 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.
%U http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/744