On hereditary Helly classes of graphs

Mostrar todas las versiones(2)

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 corre...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Groshaus, M., Szwarcfiter, J.L.
Formato: JOUR
Lenguaje:English
Materias:
Algorithms
Bicliques
Graph classes
Helly property
(e ,2e) theory
(SPM) classes
Applied (CO)
Biclique
Discrete Mathematics
Forbidden subgraphs
Induced subgraph
Neighbourhood
OF graphs
Polynomial-time
Property (S)
Computer science
Disks (structural components)
Polynomial approximation
Topology
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_14627264_v10_n1_p71_Groshaus
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_14627264_v10_n1_p71_Groshaus
record_format dspace
spelling todo:paper_14627264_v10_n1_p71_Groshaus2023-10-03T16:16:37Z On hereditary Helly classes of graphs Groshaus, M. Szwarcfiter, J.L. Algorithms Bicliques Graph classes Helly property (e ,2e) theory (SPM) classes Applied (CO) Biclique Discrete Mathematics Forbidden subgraphs Induced subgraph Neighbourhood OF graphs Polynomial-time Property (S) Computer science Disks (structural components) Polynomial approximation Topology Graph theory 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. © 2008 Discrete Mathematics and Theoretical Computer Science (DMTCS). Fil:Groshaus, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR English info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_14627264_v10_n1_p71_Groshaus
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language English
orig_language_str_mv English
topic Algorithms
Bicliques
Graph classes
Helly property
(e ,2e) theory
(SPM) classes
Applied (CO)
Biclique
Discrete Mathematics
Forbidden subgraphs
Induced subgraph
Neighbourhood
OF graphs
Polynomial-time
Property (S)
Computer science
Disks (structural components)
Polynomial approximation
Topology
Graph theory
spellingShingle Algorithms
Bicliques
Graph classes
Helly property
(e ,2e) theory
(SPM) classes
Applied (CO)
Biclique
Discrete Mathematics
Forbidden subgraphs
Induced subgraph
Neighbourhood
OF graphs
Polynomial-time
Property (S)
Computer science
Disks (structural components)
Polynomial approximation
Topology
Graph theory
Groshaus, M.
Szwarcfiter, J.L.
On hereditary Helly classes of graphs
topic_facet Algorithms
Bicliques
Graph classes
Helly property
(e ,2e) theory
(SPM) classes
Applied (CO)
Biclique
Discrete Mathematics
Forbidden subgraphs
Induced subgraph
Neighbourhood
OF graphs
Polynomial-time
Property (S)
Computer science
Disks (structural components)
Polynomial approximation
Topology
Graph theory
description 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. © 2008 Discrete Mathematics and Theoretical Computer Science (DMTCS).
format JOUR
author Groshaus, M.
Szwarcfiter, J.L.
author_facet Groshaus, M.
Szwarcfiter, J.L.
author_sort Groshaus, M.
title On hereditary Helly classes of graphs
title_short On hereditary Helly classes of graphs
title_full On hereditary Helly classes of graphs
title_fullStr On hereditary Helly classes of graphs
title_full_unstemmed On hereditary Helly classes of graphs
title_sort on hereditary helly classes of graphs
url http://hdl.handle.net/20.500.12110/paper_14627264_v10_n1_p71_Groshaus
work_keys_str_mv AT groshausm onhereditaryhellyclassesofgraphs
AT szwarcfiterjl onhereditaryhellyclassesofgraphs
_version_ 1807322540466503680

Ejemplares similares