Pairwise Compatibility Graphs: A Survey
From MaRDI portal
Publication:3186100
DOI10.1137/140978053zbMath1342.05058OpenAlexW2477819130MaRDI QIDQ3186100
Blerina Sinaimeri, Tiziana Calamoneri
Publication date: 8 August 2016
Published in: SIAM Review (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01388533/file/SurveyPCG.pdf
Applications of graph theory (05C90) General topics of discrete mathematics in relation to computer science (68R01) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Signed and weighted graphs (05C22)
Related Items (18)
Unnamed Item ⋮ New results on pairwise compatibility graphs ⋮ Recognition of linear and star variants of leaf powers is in P ⋮ Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees ⋮ Pairwise compatibility graphs: complete characterization for wheels ⋮ Exact-2-relation graphs ⋮ A method for enumerating pairwise compatibility graphs with a given number of vertices ⋮ Inferring phylogenetic trees from the knowledge of rare evolutionary events ⋮ Some classes of graphs that are not PCGs ⋮ Characterizing star-PCGs ⋮ On the enumeration of minimal non-pairwise compatibility graphs ⋮ On the enumeration of minimal non-pairwise compatibility graphs ⋮ From modular decomposition trees to rooted median graphs ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ Some reduction operations to pairwise compatibility graphs ⋮ A survey on pairwise compatibility graphs ⋮ Linear-time recognition of double-threshold graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Towards a characterization of leaf powers by clique arrangements
- Tolerance graphs
- Structure and linear time recognition of 3-leaf powers
- Rooted directed path graphs are leaf powers
- Characterising \((k,\ell )\)-leaf powers
- Exact leaf powers
- Pairwise compatibility graphs
- The complete inclusion structure of leaf power classes
- A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
- Characterizations of strongly chordal graphs
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- Decomposition of graphical sequences and unigraphs
- NeST graphs
- Neighborhood subtree tolerance graphs
- Threshold graphs and related topics
- Exploring pairwise compatibility graphs
- On pairwise compatibility graphs having Dilworth number \(k\)
- Some remarks about leaf roots
- On graphs that are not PCGs
- The number of caterpillars
- On pairwise compatibility graphs having Dilworth number two
- A decomposition theorem for partially ordered sets
- On Graph Powers for Leaf-Labeled Trees
- ON THE PAIRWISE COMPATIBILITY PROPERTY OF SOME SUPERCLASSES OF THRESHOLD GRAPHS
- On Relaxing the Constraints in Pairwise Compatibility Graphs
- DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
- The 3-Steiner Root Problem
- Threshold tolerance graphs
- Recognizing $P_4 $-Sparse Graphs in Linear Time
- Graph Classes: A Survey
- Computing Phylogenetic Roots with Bounded Degrees and Errors
- Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
- On Graphs That Are Not PCGs
- Structure and linear-time recognition of 4-leaf powers
- Ptolemaic Graphs and Interval Graphs Are Leaf Powers
- On k- Versus (k + 1)-Leaf Powers
- Algorithms and Computation
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Pairwise Compatibility Graphs: A Survey
