Ptolemaic Graphs and Interval Graphs Are Leaf Powers

DOI10.1007/978-3-540-78773-0_42zbMath1136.68450OpenAlexW1577953806MaRDI QIDQ5458553

Christian Hundt, Andreas Brandstädt

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_42

zbMATH Keywords

clique-widthstrongly chordal graphsleaf powersgraph powersleaf rootsgraph class inclusionsptolemaic graphs(unit) interval graphs

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10)

Related Items (19)

On pairwise compatibility graphs having Dilworth number two ⋮ Pairwise Compatibility Graphs: A Survey ⋮ Towards a characterization of leaf powers by clique arrangements ⋮ New results on pairwise compatibility graphs ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Recognition of linear and star variants of leaf powers is in P ⋮ Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ Exact-2-relation graphs ⋮ Parameterized Leaf Power Recognition via Embedding into Graph Products ⋮ On pairwise compatibility graphs having Dilworth number \(k\) ⋮ Rooted directed path graphs are leaf powers ⋮ Characterising \((k,\ell )\)-leaf powers ⋮ Some classes of graphs that are not PCGs ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Simplicial powers of graphs ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Simplicial Powers of Graphs ⋮ A survey on pairwise compatibility graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Consecutive retrieval property -- revisited
• Structure and linear time recognition of 3-leaf powers
• Strictly chordal graphs are leaf powers
• Characterizations of strongly chordal graphs
• Distance-hereditary graphs
• Neighborhood subtree tolerance graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Some remarks about leaf roots
• Error compensation in leaf power problems
• On Graph Powers for Leaf-Labeled Trees
• Distance-Hereditary 5-Leaf Powers
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• The 3-Steiner Root Problem
• On (k,ℓ)-Leaf Powers
• A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices
• A characterization of ptolemaic graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Structure and linear-time recognition of 4-leaf powers
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Ptolemaic Graphs and Interval Graphs Are Leaf Powers