INVESTIGADORES
DE CARIA DI FONZO Pablo Jesus
artículos
Título:
Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs
Autor/es:
DE CARIA, PABLO
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2022 vol. 323 p. 171 - 183
ISSN:
0166-218X
Resumen:
This paper is inspired by the well known characterization of chordal graphs as theintersection graphs of subtrees of a tree. We consider families of induced trees of anygraph 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 the intersection graph of induced trees of abipartite graph and we characterize some classes that arise when we impose restrictionson the host bipartite graph.
