Artículo

Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs

de Caria, Pablo JesúsIcon
Fecha de publicación: 12/2022
Editorial: Elsevier Science
Revista: Discrete Applied Mathematics
ISSN: 0166-218X
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

This paper is inspired by 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.
Palabras clave: BIPARTITE GRAPH , CHORDAL GRAPH , CLIQUE REPRESENTATION , CLIQUE TREE , INTERSECTION GRAPH , SUBTREE
 
Archivos asociados
Tamaño: 1.148Mb
Formato: PDF
.
Licencia
info:eu-repo/semantics/restrictedAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/186989
DOI: http://dx.doi.org/10.1016/j.dam.2021.04.006
URL: https://www.sciencedirect.com/science/article/pii/S0166218X21001487
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
de Caria, Pablo Jesús; Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs; Elsevier Science; Discrete Applied Mathematics; 323; 12-2022; 171-183
Compartir
Altmétricas