A survey on pairwise compatibility graphs

DOI10.1016/j.akcej.2019.12.011zbMath1475.05077OpenAlexW3037663231MaRDI QIDQ5012383

Md. Saidur Rahman, Shareef Ahmed

Publication date: 1 September 2021

Published in: AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.akcej.2019.12.011

zbMATH Keywords

phylogenetic treespairwise compatibility graphsleaf power graphsmulti-interval pairwise compatibility graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (3)

New results on pairwise compatibility graphs ⋮ Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ On star-multi-interval pairwise compatibility graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Towards a characterization of leaf powers by clique arrangements
• Tolerance graphs
• Computing phylogenetic roots with bounded degrees and errors is NP-complete
• Rooted directed path graphs are leaf powers
• Pairwise compatibility graphs
• Characterizations of strongly chordal graphs
• The Steiner problem in phylogeny is NP-complete
• Graphs that are not pairwise compatible: a new proof technique (extended abstract)
• Exploring pairwise compatibility graphs
• Basic graph theory
• On graphs that are not PCGs
• On pairwise compatibility graphs having Dilworth number two
• A decomposition theorem for partially ordered sets
• A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
• 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
• Multi-interval Pairwise Compatibility Graphs
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Pairwise Compatibility Graphs: A Survey
• Graph Classes: A Survey
• Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
• The complexity of satisfiability problems
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
• Graph Drawing
• Characterizing star-PCGs

This page was built for publication: A survey on pairwise compatibility graphs