Families of induced trees and their intersection graphs

This paper is inspired in the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. We consider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact is that the concept of clique tree of chorda...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: De Caria, Pablo Jesús
Formato: Articulo
Lenguaje:Inglés
Publicado: 2019
Materias:
Matemática
Subtree
Intersection Graph
Clique Tree
Bipartite Graph
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/159867
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-159867
record_format dspace
spelling I19-R120-10915-1598672023-11-07T20:07:17Z http://sedici.unlp.edu.ar/handle/10915/159867 Families of induced trees and their intersection graphs De Caria, Pablo Jesús 2019 2023-11-07T14:57:31Z en Matemática Subtree Intersection Graph Clique Tree Bipartite Graph This paper is inspired in the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. We consider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact is that the concept of clique tree of chordal graphs cannot be widely generalized. Finally, we consider the fact that every graph is the intersection graph of induced trees of a bipartite graph and we characterize some classes that arise when we impose restrictions on the host bipartite graph. Facultad de Ciencias Exactas Articulo Articulo http://creativecommons.org/licenses/by-nc-nd/4.0/ Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) application/pdf
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Subtree
Intersection Graph
Clique Tree
Bipartite Graph
spellingShingle Matemática
Subtree
Intersection Graph
Clique Tree
Bipartite Graph
De Caria, Pablo Jesús
Families of induced trees and their intersection graphs
topic_facet Matemática
Subtree
Intersection Graph
Clique Tree
Bipartite Graph
description This paper is inspired in the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. We consider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact is that the concept of clique tree of chordal graphs cannot be widely generalized. Finally, we consider the fact that every graph is the intersection graph of induced trees of a bipartite graph and we characterize some classes that arise when we impose restrictions on the host bipartite graph.
format Articulo
Articulo
author De Caria, Pablo Jesús
author_facet De Caria, Pablo Jesús
author_sort De Caria, Pablo Jesús
title Families of induced trees and their intersection graphs
title_short Families of induced trees and their intersection graphs
title_full Families of induced trees and their intersection graphs
title_fullStr Families of induced trees and their intersection graphs
title_full_unstemmed Families of induced trees and their intersection graphs
title_sort families of induced trees and their intersection graphs
publishDate 2019
url http://sedici.unlp.edu.ar/handle/10915/159867
work_keys_str_mv AT decariapablojesus familiesofinducedtreesandtheirintersectiongraphs
_version_ 1807221782501916672

Ejemplares similares