INVESTIGADORES
DE CARIA DI FONZO Pablo Jesus
artículos
Título:
Families of induced trees and their intersection graphs
Autor/es:
PABLO DE CARIA
Revista:
Electronic Notes in Theoretical Computer Science
Editorial:
Elsevier
Referencias:
Año: 2019 vol. 346 p. 265 - 274
ISSN:
1571-0661
Resumen:
This paper is inspired in the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. Weconsider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact isthat the concept of clique tree of chordal graphs cannot be widely generalized. Finally, we consider the fact that every graph is theintersection graph of induced trees of a bipartite graph and we characterize some classes that arise when we impose restrictionson the host bipartite graph.
