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

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

Authors: Groshaus, Marina and Szwarcfiter, Jayme Luiz

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.


Source : oai:HAL:hal-00972306v1
Volume: Vol. 10 no. 1
Section: Graph and Algorithms
Published on: January 1, 2008
Submitted on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 36 times.
This article's PDF has been downloaded 22 times.