Upload resources

Upload your works to SEDICI to increase its visibility and improve its impact

 

Show simple item record

dc.date.accessioned 2023-11-07T14:57:31Z
dc.date.available 2023-11-07T14:57:31Z
dc.date.issued 2019
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/159867
dc.description.abstract 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. en
dc.language en es
dc.subject Subtree es
dc.subject Intersection Graph es
dc.subject Clique Tree es
dc.subject Bipartite Graph es
dc.title Families of induced trees and their intersection graphs en
dc.type Articulo es
sedici.identifier.other https://doi.org/10.1016/j.entcs.2019.08.024 es
sedici.identifier.issn 1571-0661 es
sedici.creator.person De Caria, Pablo Jesús es
sedici.subject.materias Matemática es
sedici.description.fulltext true es
mods.originInfo.place Facultad de Ciencias Exactas es
sedici.subtype Articulo es
sedici.rights.license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
sedici.rights.uri http://creativecommons.org/licenses/by-nc-nd/4.0/
sedici.description.peerReview peer-review es
sedici.relation.journalTitle Electronic Notes in Theoretical Computer Science es
sedici.relation.journalVolumeAndIssue vol. 346 es


Download Files

Thumbnail
Documento completo
Download file (475.8Kb) - PDF

This item appears in the following Collection(s)

Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Except where otherwise noted, this item's license is described as Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)