Ptolemaic Graphs and Interval Graphs Are Leaf Powers

DOI10.1007/978-3-540-78773-0_42MaRDI QIDQ5458553zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Christian Hundt

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

(unit) interval graphsclique-widthgraph class inclusionsgraph powersleaf powersleaf rootsptolemaic graphsstrongly chordal graphs

Mathematics Subject Classification ID

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

Recommendations

• Rooted directed path graphs are leaf powers
• Exact leaf powers
• Characterising \((k,\ell )\)-leaf powers
• On (k,ℓ)-Leaf Powers
• Structure and linear time recognition of 3-leaf powers

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A characterization of ptolemaic graphs
• A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices
• Characterizations of strongly chordal graphs
• Coloring powers of graphs of bounded clique-width.
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Consecutive retrieval property -- revisited
• Distance-Hereditary 5-Leaf Powers
• Distance-hereditary graphs
• Error compensation in leaf power problems
• Graph Classes: A Survey
• scientific article; zbMATH DE number 4077265 (Why is no real title available?)
• scientific article; zbMATH DE number 165077 (Why is no real title available?)
• scientific article; zbMATH DE number 2080275 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Neighborhood subtree tolerance graphs
• On (k,ℓ)-Leaf Powers
• On graph powers for leaf-labeled trees
• On the clique-width of some perfect graph classes
• Some remarks about leaf roots
• Strictly chordal graphs are leaf powers
• Structure and linear time recognition of 3-leaf powers
• Structure and linear-time recognition of 4-leaf powers
• The 3-Steiner Root Problem
• The Clique-Width of Tree-Power and Leaf-Power Graphs
• Topics in Intersection Graph Theory

Cited in

(22)

• 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
• New results on pairwise compatibility graphs
• Exact-2-relation graphs
• On pairwise compatibility graphs having Dilworth number k
• Some classes of graphs that are not PCGs
• On pairwise compatibility graphs having Dilworth number two
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• Pairwise compatibility graphs: a survey
• Parameterized leaf power recognition via embedding into graph products
• A survey on pairwise compatibility graphs
• Simplicial Powers of Graphs
• Recognition of linear and star variants of leaf powers is in P
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Boxicity of leaf powers
• Computing optimal leaf roots of chordal cographs in linear time
• On generalizations of pairwise compatibility graphs
• On star-k-PCGs: exploring class boundaries for small k values
• Parameterized leaf power recognition via embedding into graph products
• Rooted directed path graphs are leaf powers
• Characterising \((k,\ell )\)-leaf powers

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

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