Marina Groshaus ; Jayme Luiz Szwarcfiter - On hereditary Helly classes of graphs

dmtcs:440 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 1 - https://doi.org/10.46298/dmtcs.440
On hereditary Helly classes of graphs

Authors: Marina Groshaus ; Jayme Luiz Szwarcfiter

    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.


    Volume: Vol. 10 no. 1
    Section: Graph and Algorithms
    Published on: January 1, 2008
    Imported on: March 26, 2015
    Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Share

    Consultation statistics

    This page has been seen 163 times.
    This article's PDF has been downloaded 136 times.