On Hereditary Helly classes of graphs
Marina Groshaus, Jayme Luiz Szwarcfiter
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.
Full Text: PDF PostScript