Ptolemaic Graphs and Interval Graphs Are Leaf Powers
DOI10.1007/978-3-540-78773-0_42zbMATH Open1136.68450OpenAlexW1577953806MaRDI QIDQ5458553FDOQ5458553
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
Recommendations
clique-widthstrongly chordal graphsleaf powersgraph powersleaf rootsgraph class inclusionsptolemaic graphs(unit) interval graphs
Problems related to evolution (92D15) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Linear time solvable optimization problems on graphs of bounded clique-width
- On the clique-width of some perfect graph classes
- Characterizations of strongly chordal graphs
- Distance-hereditary graphs
- Consecutive retrieval property -- revisited
- A characterization of ptolemaic graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Title not available (Why is that?)
- Neighborhood subtree tolerance graphs
- Some remarks about leaf roots
- Error compensation in leaf power problems
- On graph powers for leaf-labeled trees
- 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
- Structure and linear-time recognition of 4-leaf powers
- Structure and linear time recognition of 3-leaf powers
- Title not available (Why is that?)
- Computing Phylogenetic Roots with Bounded Degrees and Errors
- Title not available (Why is that?)
- Strictly chordal graphs are leaf powers
- Coloring powers of graphs of bounded clique-width.
- Distance-Hereditary 5-Leaf Powers
Cited In (20)
- On pairwise compatibility graphs having Dilworth number \(k\)
- Some classes of graphs that are not PCGs
- A survey on pairwise compatibility graphs
- Boxicity of leaf powers
- Recognition of linear and star variants of leaf powers is in P
- Recognizing k -Leaf Powers in Polynomial Time, for Constant k
- Simplicial powers of graphs
- On pairwise compatibility graphs having Dilworth number two
- Pairwise compatibility graphs: a survey
- Computing optimal leaf roots of chordal cographs in linear time
- Characterising \((k,\ell )\)-leaf powers
- New results on pairwise compatibility graphs
- Closest 4-leaf power is fixed-parameter tractable
- The NLC-width and clique-width for powers of graphs of bounded tree-width
- Parameterized leaf power recognition via embedding into graph products
- Exact-2-relation graphs
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- Simplicial Powers of Graphs
- Parameterized leaf power recognition via embedding into graph products
- Rooted directed path graphs are 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)
