A survey on pairwise compatibility graphs

DOI10.1016/J.AKCEJ.2019.12.011MaRDI QIDQ5012383zbMATH OpenOpenAlexFDO

Authors Md. Saidur Rahman, Shareef Ahmed

Publication date 1 September 2021

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

Copyright license Creative Commons Attribution 4.0 International

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)

Recommendations

• Pairwise compatibility graphs: a survey
• Pairwise compatibility graphs
• Pairwise Compatibility Graphs
• Exploring pairwise compatibility graphs
• On graphs that are not PCGs

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 2080275 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• A necessary condition and a sufficient condition for pairwise compatibility graphs
• A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application
• Basic graph theory
• Characterizations of strongly chordal graphs
• Computing phylogenetic roots with bounded degrees and errors is NP-complete
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Exploring pairwise compatibility graphs
• Graph Classes: A Survey
• Graph Drawing
• Graphs that are not pairwise compatible: a new proof technique (extended abstract)
• Multi-interval pairwise compatibility graphs (extended abstract)
• On graph powers for leaf-labeled trees
• On graphs that are not PCGs
• On pairwise compatibility graphs having Dilworth number two
• On relaxing the constraints in pairwise compatibility graphs
• On the pairwise compatibility property of some superclasses of threshold graphs
• Pairwise compatibility graphs
• Pairwise compatibility graphs: a survey
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Rooted directed path graphs are leaf powers
• The Steiner problem in phylogeny is NP-complete
• The complexity of satisfiability problems
• Tolerance graphs
• Triangle-free outerplanar 3-graphs are pairwise compatibility graphs

Cited in

(14)

• Triangle-free outerplanar 3-graphs are pairwise compatibility graphs
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Pairwise Compatibility Graphs
• Pairwise compatibility graphs
• On star-multi-interval pairwise compatibility graphs
• Exact-2-relation graphs
• A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
• A method for enumerating pairwise compatibility graphs with a given number of vertices
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Pairwise compatibility graphs: complete characterization for wheels
• New results on pairwise compatibility graphs
• Multi-interval pairwise compatibility graphs (extended abstract)
• Pairwise compatibility graphs: a survey
• Discovering pairwise compatibility graphs

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

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