Families of Induced Trees and Their Intersection Graphs | Zendy

Pablo De Caria | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Families of Induced Trees and Their Intersection Graphs

Author(s) -

Pablo De Caria

Publication year - 2019

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2019.08.024

Subject(s) - chordal graph , combinatorics , block graph , mathematics , split graph , intersection graph , bipartite graph , distance hereditary graph , discrete mathematics , interval graph , treewidth , tree depth , cograph , outerplanar graph , clique graph , clique width , indifference graph , pathwidth , line graph , graph , 1 planar graph , voltage graph

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research