Back to Search Start Over

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

Authors :
De Caria, Pablo
Source :
Discrete Applied Mathematics. Dec2022, Vol. 323, p171-183. 13p.
Publication Year :
2022

Abstract

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
0166218X
Volume :
323
Database :
Academic Search Index
Journal :
Discrete Applied Mathematics
Publication Type :
Academic Journal
Accession number :
159926208
Full Text :
https://doi.org/10.1016/j.dam.2021.04.006