Recognising the overlap graphs of subtrees of restricted trees is hard

MaRDI QIDQ6621196zbMATH OpenFDO

Authors Jessica Enright, Martin Pergel

Publication date 18 October 2024

Published in Acta Mathematica Universitatis Comenianae. New Series (Search for Journal in Brave)

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Equivalence of the filament and overlap graphs of subtrees of limited trees
• Algorithms on subgraph overlap graphs
• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
• The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
• Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• A faster algorithm to recognize undirected path graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Chordal Graphs as Intersection Graphs of Pseudosegments
• Equivalences and the complete hierarchy of intersection graphs of paths in a tree
• Graph Drawing
• Intersection graphs of paths in a tree
• Linear algorithms for chordal graphs of bounded directed vertex leafage
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Subtree filament graphs are subtree overlap graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The vertex leafage of chordal graphs

This page was built for publication: Recognising the overlap graphs of subtrees of restricted trees is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6621196)