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 -
On hereditary Helly classes of graphsArticle

Authors: Marina Groshaus 1; Jayme Luiz Szwarcfiter 2

  • 1 Departamento de Computación [Buenos Aires]
  • 2 Instituto de Matemática da Universidade Federal do Rio de Janeiro

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]

Consultation statistics

This page has been seen 296 times.
This article's PDF has been downloaded 249 times.